Комбинаторные задачи с ограничениями
Рассмотрим несколько типов задач, в которых на комбинации накладываются определенные ограничения.
а) Задача о львах и тиграх. Имеется 5 львов и 4 тигра. Необходимо их расставить в ряд, но при этом известно, что тигр не может идти спокойно зa тигром. Тогда расставляем львов с промежутками ( их будет 6) и в них вставляем тигров. Таким образом, если тигры и львы обезличенные, то = 15. В общем случае при n львах и k тиграх имеем:
б) Задача о книжной полке. Из m книг, стоящих на полке, нужно выбрать k таких, которые не стояли рядом на книжной полке. Отберем сразу k книг, останется n - k. Их расставим с промежутками (n - k+1 промежуток). На эти места вставим k книг. Общее решение:
(9)
в) Рыцари короля Артура. 12 рыцарей сидят за круглым столом. Нужно выбрать 5 из них, но таких, которые не сидели рядом за столом. Множество всех решений разбиваем на два подмножества в зависимости от того, входит ли в команду избранных конкретный рыцарь или нет? Ответ: 15 +21 = 36. Если за круглым столом сидит n рыцарей, а нужно выбрать k, которые не сидели рядом, то задача решается аналогично и имеет смысл при
n > 2k.
Упражнение
Определите условия при которых задачи а), б) и в) имеют решения.