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