Page 194 - 4496

5.13 Задача про караван
Розглянемо ще одну задачу, в якій рішення може бути
одержано за допомогою головної теореми комбінаторики. 9
верблюдів йдуть гусаком. Скільки існує комбінацій
перестановки верблюдів, при яких жоден верблюд не йде за
тим, за ким йшов раніше.
Виділимо заборонені пари: (1,2), (2,3), (3,4), (4,5), (5,6),
(6,7), (7,8) (8,9). Для вирішення застосуємо головну теорему
комбінаторики. Для цього визначимо, що є об'єкт і що є
властивості. Під об'єктами розумітимемо різні розстановки
верблюдів. Всього їх буде N = 9!. Під властивостями
розумітимемо наявність певної пари в перестановці. Таким
чином число властивостей рівне 8. Тоді кількість
перестановок, що не володіють жодним з 8 властивостей:

N ) 8 (  ! 9 C  8 1 ! 8 C  8 2 ! 7 C  8 3 ! 6  ... C  8 4 ! 1  142729  D  D 8
9
в загальному випадку при n верблюдах маємо
D n D n 1 
Вправа. Розглянемо послідовність чисел а 1, а 2, ..., а 10. В
якому числі перестановок цих чисел не зустрінеться жодної
пари сусідніх чисел, тобто пара (а 1, а 2), (а 2, а 3), ..., (а 9, а 10)?

5.14 Комбінаторика розбиття
При аналізі стратегій різних ігор вимагається
підраховувати кількість комбінацій при розкладі певних
предметів. Найпоширеніша карткова гра - преферанс. В
класичному варіанті цієї гри карти розкладаються на 3 купки
(по числу граючих) і 2 карти кладуться в "прикуп". Грають 32
картами, тобто кожний гравець одержує по 10 карт.
Визначимо кількість варіантів розкладу при грі в
преферанс:
32 !
N 
( 10 ) ! 3 ! 2
Для обґрунтовування одержаної формули розставимо всі
карти підряд і переставимо їх 32! способами. При кожній
перестановці виділятимемо перші 10 карт першому гравцю,
другу десятку - другому, третиною - третьому, а останні 2
191