Як вирішувати комбінаторні задачі
Дане питання можна розглянути як з точки зору стандартних методів і підходів комбінаторики, так і з застосуванням теорії ймовірності. Це дозволяє дещо розширити кругозір, а також поглянути на поставлену задачу з нестандартною точки зору.
1
Як відомо, ймовірність простих подій визначається за класичною формулою Р (А) = m / n, в якій число подій (результатів) звичайно і рівно можливих. При цьому n - загальне число випадків, а m - число сприятливих результатів (умові завдання). Тепер, необхідно розглянути три найбільш поширені формули комбінаторики: перестановки, поєднання і розміщення.
2
ПерестановкіПредставьте собі, що на столі лежать п`ять карток, на невидимій стороні яких написані цифри: 1, 2, 3, 4 і 5. Довільним чином, по одній, вони виймаються, перевертаються і укладаються по черзі. Яка ймовірність того, що витягнута комбінація буде числом 12345? Кількість сприятливих результатів m очевидно - m = 1. У той час як усього варіантів n = 5! = 120, де «!» - Знак факторіала буде цілих 120, а шукана ймовірність даної події Р = 1/120, відповідно. В даному прикладі загальне число випадків шукали як число всіляких перестановок п`яти елементів по п`яти позиціях. Тому і в якому випадку n елементів це число називають числом перестановок і позначають Pn (Pn = n!)
3
СочетаніяСледует розглянути наступний приклад. В кошику знаходиться кілька куль двох кольорів, рівне n. У такій постановці завдання, число поєднань з n елементів по m називають безліч способів, що відрізняються один від одного кількістю куль різного кольору в кожній комбінації. При цьому n - загальне число куль (елементів), m - число елементів в витягнутої комбінації. Комбінації різні, якщо вони відрізняються хоча б одним елементом. Позначення числа сполучень і формула для обчислення наведені на малюнку 1.
4
Імовірно, необхідно обчислити ймовірність виграшу в спортлото 6 з 49, де «угадано» 4 з 6-ти. Очевидно, що при цьому використовується формула для сочетанія.Общее число випадків С (з 49 по 6) = 49! / 43! 6! Сприятливий число випадків можна знайти з таких міркувань. Є 6 «хороших» із загальної кількості 49 номерів. З питання завдання досить 4-х збігів. З 6-ти «хороших» 4 можна вибрати С (з 6 по 4) способами. При цьому з решти 43 «поганих» вибираються 2 для доповнення обраної комбінації до шести елементів С (з 43 ПО2) способами. Звучить це в такий спосіб.
5
Число сприятливих ситуацій збирається як С (з 6 по 4) і С (з 37 по 2) (ситуація логічного множення). Значить m = С (з 6 по 4) С (з 43 по 2). Таким чином, ймовірність навіть самого «мізерного» виграшу Р = m / n = С (з 6 по 4) С (з 43 по 2) / С (з 49 по 6) = (6! / 2! 4!) ( 43! / 2! 41!) / (49! / 6! 43!) = 15 * 21 * 43/66 * 92 * 47 * 49 = 9 * 43/92 * 47 * 154 = 0,000347.
6
РазмещеніяЕслі в завданню про поєднаннях врахувати порядок проходження елементів в обраній комбінації з m елементів, то постане завдання про розміщення. Питання, на підставі якого приймається рішення про застосування формули числа сполучень повинен додатково (у порівнянні з поєднаннями) містити дані про необхідність урахування порядку розташування елементів в обираних комбінаціях. Якщо вибрано m елементів, то обчислюючи число розміщень необхідно число поєднань помножити на число перестановок Pm = m !. Позначення числа розміщень і формули для його обчислення дані на рис. 2.
Рада 2: Як вирішувати завдання з комбінаторики
Рішення задач на знаходження різних комбінацій являє непідробний інтерес, а комбінаторика застосовується в багатьох областях науки, наприклад, в біології для розшифровки коду ДНК або на спортивних змаганнях для розрахунку кількості ігор між учасниками.
Вам знадобиться
- калькулятор
Інструкція
1
Перестановки без повторень - це такі комбінації з n-го кількості різних елементів, в яких кількість елементів залишається рівним n, а порядок їх змінюється різними способами. P (n) = 1 * 2 * 3 * ... * n = n! Приклад
Скільки перестановок можна скласти з цифр 5,8,9? з умови завдання n = 3 (три цифри 5,8,9). Скористаємося формулою для розрахунку можливої кількості перестановок без повторень: P_ (n) = n!
Підставивши в формулу n = 3, отримаємо P = 3! = 1 * 2 * 3 = 6
Скільки перестановок можна скласти з цифр 5,8,9? з умови завдання n = 3 (три цифри 5,8,9). Скористаємося формулою для розрахунку можливої кількості перестановок без повторень: P_ (n) = n!
Підставивши в формулу n = 3, отримаємо P = 3! = 1 * 2 * 3 = 6
2
Перестановки з повтореннями - це такі комбінації з n-го кількості елементів (в тому числі і повторюваних), в яких кількість елементів залишається рівним n, а порядок їх змінюється різними способамі.Рn = n! / N1! * N2! * ... * Nk !
де n - загальна кількість елементів, n1, n2 ... nk - кількість повторюваних елементів
де n - загальна кількість елементів, n1, n2 ... nk - кількість повторюваних елементів
3
Сполучення без повторень - це всі можливі комбінації (групи) з n різних елементів по m в кожній групі (m? N), які відрізняються один від одного тільки складом елементів (групи відрізняються один від одного хоча б одним елементом).
С = n! / M! (N - m)!
С = n! / M! (N - m)!
4
Сполучення з повтореннями - це всі можливі комбінації (групи) з n різних елементів по m кожній групі (m - будь-який), причому допускається повторення одного елементу кілька разів (групи відрізняються один від одного хоча б одним елементом)
С = (n + m - 1)! / M! (N-1)!
С = (n + m - 1)! / M! (N-1)!
5
Розміщення без повторень - це всі можливі комбінації (групи) з n різних елементів по m в кожній групі (m? N), які розрізняються між собою як складом елементів, що входять до груп, так і їх порядком.
А = n! / (N - m)!
А = n! / (N - m)!
6
Розміщення c повтореннями - це всі можливі комбінації (групи) з n різних елементів по m кожній групі (m - будь-який), які розрізняються між собою як складом елементів, що входять до груп, так і їх порядком, в яких також допускається повторення елементів.
А = n ^ m
А = n ^ m
Статті за темою "Як вирішувати комбінаторні задачі"
Оцініть, будь ласка статтю
Ще статті розділу