Приклади розв'язування комбінаторних задач

1. Обчислити кількість перестановок з 5 елементів.

Розв'язування

За формулою (1.2) при п = 5 маємо

2. Обчислити кількість сполучень із 5 елементів по 3.

Розв'язування

За формулою (1.3) при n = 5 і k = 3 маємо

3.Обчислити кількість розміщень з 5 елементів по 3.

Розв'язування

За формулою (1.1) при n = 5 і k = 3 маємо

Основні поняття

Класифікація подій

Експериментом (дослідом, спробою) називається реалізація певного комплексу умов, який може повторюватись необмежене число разів. При цьому комплекс умов містить у собі випадкові чинники, реалізація яких у кожній спробі призводить до неоднозначності результату спроби.

Наприклад: експеримент - підкидання монети.

Результатом експерименту є подія.

Подія бувають:

- достовірні (завжди відбуваються в результаті експерименту);

- неможливі (ніколи не відбуваються);

- випадкові (можуть відбутися або не відбутися в результаті спроби).

Наприклад: При підкиданні кубика неможлива подія - кубик стане на ребро, випадкова подія - випадання якої-небудь грані.

Конкретний результат спроби має назву елементарної події (ω).

Наприклад: Спроба - підкидання шестигранного кубика. Елементарна подія - випадання грані з “1” або “2”.

У результаті спроби відбуваються тільки елементарні події.

Сукупність усіх можливих результатів спроби має назву простір елементарних подій (Ω), тобто сукупність елементарних подій це простір елементарних подій.

Складною подією називається довільна підмножина простору елементарних подій.

Складна подія в результаті спроби наступає тоді і тільки тоді, коли в результаті спроб відбулася елементарна подія, що належить їй.

Таким чином, якщо в результаті спроби може відбутися тільки одна елементарна подія, то в результаті досліду відбуваються всі складні події, до складу який входить ця елементарна подія.

Наприклад: спроба - підкидання кубика. Елементарна подія - випадання грані з номером “1”. Складна подія – випадання грані, некратної двом.

Приклад 1.

Кидають одночасно дві гральні кістки. Знайти загальне число ісходів і число ісходів, які сприяють подіям:

1) А - сума очок, які випали дорівнює 8.

2) В – добуток очок, що випали, дорівнює 8.

3) С - сума очок, що випали, дорівнює 8 , а добуток 15.

Розв’язання:

1). Загальне число можливих елементарних ісходів досліду дорівнює n=6×6 = 36, тому що кожна кістка дає 6 наслідків, а кожний з наслідків підкидання "першої" кістки може поєднуватися з кожним з наслідків підкидання "другої". Сприятливими нашій події (сума очок дорівнює 8) наслідками є такі: (2;6), (3;5), (4,4); (5;3); (6;2) тобто т = 5.

2) Загальна кількість можливих елементарних наслідків досліду залишилося тим самим, т.б. n = 36, а число наслідків, які сприяють події B m=2, {(2;4),(4;2)} .

1) Загальна кількість можливих елементарних наслідків досліду n = 36. Сприяють шуканій події тільки ті наслідки, у яких виконуються дві умови: сума очок дорівнює 8, а добуток дорівнює 15: {(3;5),(5;3)}, т. б. m = 2

Теорія ймовірностей займається вивченням випадкових подій, введемо їх класифікацію.

Дві або декілька подій називають рівноможливими, якщо умови їх появи однакові і немає підстави вважати, що одна з них має більше шансів з'явитися, ніж інші.

Дві або декілька подій називають несумісними, якщо поява однієї з них виключає появу інших.

Дві або декілька подій називають сумісними, якщо поява однієї з них не виключає появи інших.

Дві або декілька подій називають незалежними, якщо поява однієї з них не впливає на появу інших.

Дві або декілька подій називають залежними, якщо поява однієї з них впливає на появу інших.

Якщо простір елементарних наслідків складається тільки з двох несумісних подій, то такі події називають протилежними (А і Ā).

Події утворюють повну групу, якщо наслідком досліду стає одна з них.

Введемо такі позначення:

А - подія;

- елементи простору W;

W- простір елементарних подій;

U, W - простір елементарних подій як достовірна подія;

V - неможлива подія;

Ā - подія, протилежна події А.

Операції над подіями.

1. Подія C називається сумою A+B, якщо вона складається з усіх елементарних подій, що входять як в A, так і в B. При цьому якщо елементарна подія входить і в A, і в B, тоді в C вона входить один раз. У результаті досліду подія C відбувається тоді, коли відбулася подія, що входить або в A або в B. Сума довільної кількості подій складається з усіх елементарних подій, що входять в одне з A_i, i = 1, ... , m.

W

2. Подія C називається добутком подій A і B, якщо вона складається з усіх елементарних подій, що входять і в A, і в B. Добутком довільного числа подій називають подію, яка складається з елементарних подій, що входять в усі A_i, i =1, ... , m.

3. Різницею подій A - B називають подію C, що складається з усіх елементарних подій, що входять в A, але не входять в B.

Властивості операцій:

1.Ø

2.Ø+А=А

3.

4.А+В=В+А

5.(А+В)+С=А+(В+С)

6.

7.А*Ø=Ø

8.

9.

10.

11.

12.

13.

14.

15. Ø

16.

17. - закони де Моргана

Частота випадкової події.

Нехай простір елементарних подій скінчений і складається з m елементарних подій. У цьому випадку в якості можливих наслідків розглядають 2 подій - множина всіх підмножин простору елементарних подій W і неможлива подія V.

Приклад:

W=(w₁, w₂, w₃₎

A₁=V

A₂=(w₁₎

A₃=(w₂₎

A₄=(w₃₎

A₅=(w₁, w₂₎

A₆=(w₂, w₃₎

A₇=(w₁, w₃₎

A₈=(w₁, w₂, w₃₎

Позначимо систему цих подій через F. Беремо довільну подію AÎF. Проводимо серію дослідів у кількості n. n - це кількість дослідів, у кожному з який відбулася подія A.

Частотою випадкової події A у n спробах називають число

_.

Властивості частоти:

1.

2. Частота достовірної події дорівнює 1. W_n(U)=1.

3. Частота суми попарно несумісних подій дорівнює сумі частот.

Розглянемо систему Ai, i = 1, ... , k; події попарно несумісні, тобто . Подія, .

Нехай у результаті деякого досліду відбулася подія A. З визначення суми це означає, що в цьому досліді відбулася деяка подія A_i. З Того що всі події попарно несумісні, випливає, що ніяка інша подія A_j (i ¹ j) у цьому досліді відбутися не може. Отже:

n = nA +nA +... +nA

.

Теорія ймовірності використовується при описі тільки таких дослідів, для яких виконується таке припущення:

Для будь-якої події A частота випадкової події в будь-якій нескінченній серії дослідів має границю, яка має назву ймовірність випадкової події A.

Отже, якщо розглядається ймовірність випадкової події, то ми розуміємо це число так: це частота випадкової події в нескінченній (достатньо великій) серії дослідів.

На жаль, спроба визначити ймовірність як границю частоти, при кількості дослідів, що прямують до нескінченності, закінчилася невдало. Хоча американський вчений Мізес створив теорію ймовірності, що базується на цьому визначенні, але її не визнали через велику кількість внутрішніх логічних невідповідностей.

Теорія ймовірності як наука була побудована на аксіоматиці Колмогорова.