Задача 60442

Темы:    [ Формула включения-исключения ] [ Раскладки и разбиения ] [ Правило произведения ] [ Сочетания и размещения ]

Сложность: 3+ Классы: 8,9,10

Условие

Сколькими способами можно расселить 15 гостей в четырёх комнатах, если требуется, чтобы ни одна из комнат не осталась пустой?

Решение

Без указанного ограничения есть 4¹⁵ способов. В 3¹⁵ из них первая (вторая, третья, четвертая) комната будет пуста. В 2¹⁵ способов будет пуста фиксированная пара комнат, и по одному способу, когда три фиксированные комнаты будут пусты. По формуле включения-исключения (см. задачу 60435) имеется  4¹⁵ – 4·3¹⁵ + 6·2¹⁵ – 4  способа, когда все комнаты непусты.

Ответ

4¹⁵ – 4·3¹⁵ + 6·2¹⁵ – 4  способа.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	2
Название	Комбинаторика
Тема	Комбинаторика
параграф
Номер	4
Название	Формула включений и исключений
Тема	Формула включения-исключения
задача
Номер	02.108