Очень Голодная Гусеница составляет себе меню на ближайшие 10 дней. Каждый день она хочет съесть один фрукт. У нее есть такой набор фруктов: груша, 5 яблок и 4 сливы. Сколькими способами она может составить меню так, чтобы никакие два дня подряд не есть фрукт одного и того же вида?

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи можно использовать принцип включений-исключений.

Обозначим:

A1: количество способов выбрать фрукт груша два дня подрядA2: количество способов выбрать фрукт яблоко два дня подрядA3: количество способов выбрать фрукт слива два дня подряд

Тогда общее количество способов выбрать фрукты без ограничений: 3 * 2^9.

Для нахождения количества способов, когда есть ограничения на два дня подряд, воспользуемся принципом включений-исключений:

количество способов, когда фрукт груша выбран два дня подряд: 2^8количество способов, когда фрукт яблоко выбран два дня подряд: 2^8количество способов, когда фрукт слива выбран два дня подряд: 2^8

По формуле включений-исключений получаем:
Общее количество способов = 3 * 2^9 - (A1 + A2 + A3) + (A1 ∩ A2 + A1 ∩ A3 + A2 ∩ A3) - A1 ∩ A2 ∩ A3

A1 = 2^8A2 = 2^8A3 = 2^8A1 ∩ A2 = 2^7A1 ∩ A3 = 2^7A2 ∩ A3 = 2^7A1 ∩ A2 ∩ A3 = 2^6

Подставляем значения в формулу:
Общее количество способов = 3 2^9 - (2^8 + 2^8 + 2^8) + (2^7 + 2^7 + 2^7) - 2^6 = 3 2^9 - 3 2^8 + 3 2^7 - 2^6 = 432

Таким образом, Очень Голодной Гусенице есть 432 способа составить меню на ближайшие 10 дней, чтобы никакие два дня подряд не есть фрукт одного и того же вида.