Задача о беспорядках

Как применение метода включений и исключений рассмотрим задачу о беспорядках или задачу о встречах, предложенную Монмором, которая представляет интерес для различных приложений.

Сколькими способами можно разместить элементов множества в ячеек множества (по одному в каждой) так, чтобы никакой элемент не попал в ячейку ?

Перестановку без повторений можно представить как биекцию множества на себя:

.

Перестановку называют беспорядком, если в ней каждый элемент стоит не на своем месте, то есть , .

Задача о беспорядках состоит в том, чтобы подсчитать число перестановок-беспорядков. Например, , .

Обозначим через множество все перестановок , в которых элемент стоит на -ом месте:

.

Множество состоит из перестановок, в которых хотя бы один элемент стоит на своем месте, а все остальные перестановки будут беспорядками. Тогда по формуле обращения

. (8)

Подсчитаем число перестановок в каждом из множеств и в их пересечениях. Если , то сужение отображения на множество является биекцией этого множества на себя. Следовательно, .

Множество составлено из перестановок , в которых , . Сужение отображения на множество является биекцией этого множества на себя. Следовательно, .

По индукции находим, что .

По формуле включений и исключений

В каждой из этих сумм слагаемые не зависят от индекса суммирования, поэтому для вычисления надо знать только их количество. В первой сумме слагаемых, число слагаемых во второй сумме равно количеству всевозможных пар , которые можно составить из индексов , то есть . Аналогично в -ой сумме имеем слагаемых. Отсюда

.

После подстановки в уравнение (8) и несложных преобразований находим

.

Выражение, стоящее в скобках, представляет собой частичную сумму ряда, сходящегося к , поэтому . Можно показать, что равно целому числу, ближайшему к : , где – целая часть числа .