Задача о письмах

У этого термина есть другое значение - см. Инверсия (перестановка).

В комбинаторике беспорядком называется перестановка без неподвижных точек.

Количество всех беспорядков порядка n может вычислено с помощью принципа включения-исключения и дается выражением:

$!n = n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\dots +(-1)^n\frac{n!}{n!} = \sum_{k=0}^n(-1)^k\frac{n!}{k!}$

которое называется субфакториалом числа n.

В виду того, что $\sum_{k=0}^\infty(-1)^k\frac{1}{k!} = \frac{1}{e}$, значение !n с ростом n ведет себя как $\frac{n!}{e}$. Более того, при n > 0 его можно представить как результат округления числа $\frac{n!}{e}$.

Вычисление количества беспорядков является популярной задачей в олимпиадной математике, которая встречается в разных формулировках таких как задача о беспорядке, задача о письмах, задача о встречах и т. д.

Задача о письмах

Если n писем случайным образом положить в n различных конвертов, то какова вероятность, что какое-то письмо попадет в свой конверт? Ответ дается выражением

$1-\frac{!n}{n!}\approx 1-\frac{1}{e}$

Таким образом, ответ слабо зависит от количества конвертов и является почти постоянной вероятностью.

См. также

• Парадокс дней рождения

Ссылки

• Р. Стенли Перечислительная комбинаторика. — М.: Мир, 1990. — С. 107-108.