Як вирішувати комбінаторні задачі


 

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



Інструкція

  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.