ЯК вирішувати комбінаторні задачі :: обчислити всі поєднання з n по m

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

Інструкція

Як відомо, ймовірність простих подій визначається за класичною формулою Р (А) = m / n, в якій число подій (результатів) звичайно і равновозможних. При цьому n - загальне число фіналів, а m - число сприятливих результатів (умові завдання). Тепер, необхідно розглянути три найбільш поширені формули комбінаторики: перестановки, поєднання і розміщення.

ПерестановкіПредставьте собі, що на столі лежать п'ять карток, на невидимій стороні яких написані цифри: 1, 2, 3, 4 і 5. Довільним чином, по одній, вони виймаються, перевертаються і укладаються по черзі. Яка ймовірність того, що витягнута комбінація буде числом 12345? Кількість сприятливих результатів m очевидно - m = 1. У той час як усього варіантів n = 5! = 120, де «!» - Знак факторіала буде цілих 120, а шукана ймовірність даної події Р = 1/120, відповідно. У даному прикладі загальне число фіналів шукали як число всіляких перестановок п'яти елементів по п'яти позиціях. Тому і в довільному випадку n елементів це число називають числом перестановок і позначають Pn (Pn = n!)

СочетаніяСледует розглянути наступний приклад. В кошику знаходиться деяка кількість куль двох кольорів, рівне n. У такій постановці завдання, число сполучень з n елементів по m називають безліч способів, що відрізняються один від одного кількістю куль різного кольору в кожній комбінації. При цьому n - загальне число куль (елементів), m - число елементів в витягнутої комбінації. Комбінації різні, якщо вони відрізняються хоча б одним елементом. Позначення числа сполучень і формула для обчислення наведені на малюнку 1.

Імовірно, необхідно обчислити вірогідність виграшу в спортлото 6 з 49, де «угадано» 4 з 6-ти. Очевидно, що при цьому використовується формула для сочетанія.Общее число фіналів С (з 49 по 6) = 49! / 43! 6! Сприятливий число фіналів можна знайти з таких міркувань. Є 6 «хороших» із загальної кількості 49 номерів. З питання завдання достатньо 4-х збігів. З 6-ти «хороших» 4 можна вибрати С (з 6 по 4) способами. При цьому з решти 43 «поганих» вибираються 2 для доповнення обраної комбінації до шести елементів С (з 43 ПО2) способами. Звучить це наступним чином.

Число сприятливих ситуацій збирається як С (з 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.

РазмещеніяЕслі в задачі про поєднаннях врахувати порядок проходження елементів в обраній комбінації з m елементів, то з'явиться задача про розміщених. Питання, на підставі якого приймається рішенням про застосування формули числа сполучень повинен додатково (порівняно з поєднаннями) містити дані про необхідність урахування порядку розташування елементів в обираних комбінаціях. Якщо вибрано m елементів, то обчислюючи число розміщень необхідно число сполучень помножити на число перестановок Pm = m !. Позначення числа розміщень і формули для його обчислення дано на рис. 2.