Задача 60441

Темы:    [ Формула включения-исключения ] [ Перестановки и подстановки ] [ Объединение, пересечение и разность множеств ]

Сложность: 3+ Классы: 9,10,11 Название задачи: Беспорядки.

Условие

В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на своё место?

Решение

Всего есть 30! перестановок учеников. Обозначим через  A_k  множество перестановок, в которых k-й ученик сидит на своём месте. Очевидно, что  A_k  состоит из 29! перестановок. Пересечение любых m из 30 множеств A_k состоит из  (30 – m)!  перестановок, а всего таких пересечений  .  По формуле включения-исключения количество перестановок, в которых хотя бы один ученик сидит на своём месте,
(то есть мощность множества   A₁ ∪ ... ∪ A₃₀)   равно

  Замечание. Как известно, число в скобках весьма близко к  ¹/_e .

Ответ

  способами.

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

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