1.5. Застосування основних формул комбінаторики до визначення ймовірності випадкових подій

Комбінаторика, або комбінаторний аналіз – це розділ математики, що розглядає задачі вибору та розташування елементів деякої, зазвичай, скінченної множини відповідно до заданих правил. Отже, якщо є множина, яка складається з \(n\) елементів (тобто потужність множини дорівнює \(n\)), то кожне таке правило визначає спосіб, за яким із елементів цієї вихідної множини побудована певна комбінаторна конфігурація. Відповідно, метою комбінаторного аналізу є визначення алгоритмів побудови комбінаторних конфігурацій, їх дослідження та кількісне розв’язання задач переліку.

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

Перестановки: Перестановками називаються комбінаторні конфігурації, що складаються з \(n\) різних елементів. Ці конфігурації відрізняються одна від одної тільки порядком розміщення цих елементів. Кількість усіх можливих перестановок для даної множини залежить від її потужності \(n\) і обчислюється за формулою: \[P_{n} = n!,\] де \(n!\) – це факторіал, який дорівнює добутку всіх натуральних чисел від 1 до \(n\) включно.

Для порожньої множини можлива єдина така конфігурація, отже, \(0! = 1.\)

Приклад 1.9

Для створення чотиризначного коду запропоновано використовувати цифри 0, 1, 2, 3 без повторення. Визначити, скільки варіантів коду можна скласти.

Розв’язання

Потужність множини становить \(n = 4\). Оскільки мова йде про використання всіх елементів множини, то дана комбінаторна конфігурація є перестановками. За формулою (1.11) кількість перестановок дорівнює:

\[P_{4} = 4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24.\]

Відповідь: існують 24 варіанти створення коду.

Розміщення

Розміщеннями називаються комбінаторні конфігурації, що складаються з \(m\) різних елементів, які були відібрані з множини потужністю \(n\) і для яких порядок їх розташування у комбінаторній конфігурації має значення. Кількість усіх можливих розміщень залежить від потужності \(n\) тієї множини, з якої дістали ці елементи, і від кількості \(m\) цих елементів. Кількість розміщень обчислюється за формулою:

\[\begin{equation} A_{n}^{m} = n \cdot \left( n - 1 \right)\left( n - 2 \right)\text{...}\left( n - m + 1 \right), m \leq n. \tag{1.12} \end{equation}\]

Оскільки \(n! = (n - m)! \cdot \ (n - m + 1) \cdot (n - m + 2) \cdot ...\cdot (n - 1) \cdot n\), то формулу (1.12) можна надати у такому вигляді:

\[A_{n}^{n} = \frac{n!}{(n - m)!}.\]

Зауважимо, що при \(m = n\), тобто розглядаються всі елементи множини, яка має потужність \(n\), і порядок розташування цих елементів має значення (за означенням розміщень), то отримуємо формулу (1.11):

\[A_{n}^{n} = \frac{n!}{(n - n)!} = \frac{n!}{0!} = n! = P_{n}.\]

Приклад 1.10

Для тестування кодового замка запропоновано вибрати 4 різних цифри з множини цифр 0, 1, 2, …, 9 і скласти з них код, не використовуючи жодної цифри двічі. Скільки існує варіантів коду?

Розв’язання

Оскільки була взята не вся множина, потужність якої дорівнює \(n = 10\), а тільки її частина \(m = 4\), і порядок розташування відібраних елементів має значення, то кількість варіантів коду визначається як кількість розміщень із 10 по 4, отже, за формулою маємо (1.13):

\[\begin{equation} A_{10}^{4} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 151\ \ 200. \tag{1.13} \end{equation}\]

Відповідь: існує 151 200 варіантів коду.

Сполучення

Якщо з множини потужністю \(n\) навмання вибирають \(m\) елементів, які відрізняються за складом, але порядок їх розташування не має значення, то така комбінаторна конфігурація називається сполученням. Кількість сполучень обчислюється за формулою:

\[\begin{equation} C_{n}^{m} = \frac{n\ !}{m\ ! \cdot \left( n - m \right)\ !},\ \ \ m \leq n. \tag{1.14} \end{equation}\]

Отже, при заданих \(n\) і \(m\) кількість сполучень менша за кількість розміщень у \(m!\) разів.

Сполучення мають таку властивість, що випливає з формули:

\[C_{n}^{m} = \frac{n!}{m! \cdot \left( n - m \right)!} = С_{n}^{n - m}.\]

Приклад 1.11

Здійснюється вибіркова перевірка якості виробів. З партії, що складається з 15 виробів, навмання відібрали 3. Скільки існує способів відібрати ті вироби, що будуть проходити перевірку?

Розв’язання

За умови задачі маємо \(n = 15,\ \ m = 3\), при цьому спосіб розташування елементів у вибірковій сукупності не має значення. Отже, кількість способів відбору визначається як кількість сполучень і дорівнює:

\[C_{15}^{3} = \frac{15!}{3! \cdot 12!} = \frac{12!\ \cdot 13 \cdot 14\cdot 15}{3!\ \cdot 12!} = \frac{13 \cdot 14 \cdot 15}{1 \cdot 2 \cdot 3} = 455.\]

Відповідь: існує 455 способів сформувати вибіркову сукупність.

Зауважимо, що кількість переміщень, розміщень і сполучень пов’язані такою рівністю:

\[A_{n}^{m} = P_{m} \cdot C_{n}^{m}.\]

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

Правило суми: Якщо кількість способів, якими деякий об’єкт \(a\) може бути вибраним із сукупності об’єктів, дорівнює \(m\), а кількість способів, якими може бути вибраним об’єкт \(b\) із сукупності об’єктів, дорівнює \(n\), то кількість способів, якими можна вибрати або об’єкт \(a\), або об’єкт \(b\), дорівнює \(m + n\).

Правило добутку: Якщо кількість способів, якими деякий об’єкт \(a\) може бути вибраним із сукупності об’єктів, дорівнює \(m\), а кількість способів, якими може бути вибраним об’єкт \(b\) із сукупності об’єктів, дорівнює \(n\), то кількість способів, якими можна вибрати пару цих об’єктів, тобто і \(a\), і \(b\), становить \(m \cdot n\). Правило добутку узагальнюється для будь-якої кількості об’єктів.

Приклад 1.12

Є набір цифр: 0, 1, 2, 3 і 4. Визначити, скільки тризначних чисел можна утворити за допомогою цих цифр, якщо в межах числа цифри можуть повторюватись.

Розв’язання

Оскільки цифри у числі можуть повторюватись, то ми не можемо скористатись наведеними вище формулами для визначення кількості комбінаторних конфігурацій. Застосуємо таку схему. На перше місце можна поставити будь-яку з заданих цифр окрім нуля, тобто існує 4 способи вибрати першу цифру. Другу цифру ми вибираємо серед 5 цифр, оскільки тепер можна використовувати 0. Отже, існує 5 способів вибрати другу цифру. Третю цифру ми теж вибираємо серед 5 цифр. За правилом добутку кількість способів скласти тризначне число із запропонованих цифр дорівнює добутку кількості способів, якими можна вибрати цифру на кожне місце в числі. Отже, маємо: \[4 \cdot 5 \cdot 5 = 100.\]

Відповідь: із запропонованих п’яти цифр можна скласти 100 тризначних чисел, якщо цифри у числі можуть повторюватись.

Приклад 1.13

За допомогою комбінаторних конфігурацій зручно визначати ймовірність випадкових подій. Розглянемо задачу, розв’язання якої свого часу розглядав Галілео Галілей в роботі «Про вихід очок при грі в кості» (1718 р.). Складання таблиці шансів при грі двома або трьома кістками викликало інтерес не тільки у гравців в азартні ігри, але й у математиків епохи Відродження. Найбільш повне розв’язання задачі про число всіх можливих результатів при киданні трьох гральних кісток дав Галілео Галілей. Розглянемо розв’язок цієї задачі за алгоритмом, який запропонував Галілей. Однак при викладенні цього алгоритму будемо користатися сучасними означеннями теорії ймовірностей.

Приклад 1.14. (Задача Галілея)

Дослідити ймовірність випадіння 9 та 10 очок при грі трьома кістками.