Беспорядок (перестановка)

У этого термина существуют и другие значения, см. Беспорядок.

Не следует путать с Инверсия (перестановка).

Беспорядок в комбинаторике — перестановка без неподвижных точек; количество беспорядков заданного числа ${\displaystyle n}$ — его субфакториал ${\displaystyle !n}$.

Пример задачи, где требуется вычислить число всех беспорядков — задача о письмах, считающаяся классикой олимпиадной математики: если ${\displaystyle n}$ писем случайным образом положить в ${\displaystyle n}$ различных конвертов, то какова вероятность, что какое-нибудь из писем попадёт в свой конверт? Ответ даётся выражением:

${\displaystyle 1-{\frac {!n}{n!}}}$, при этом при увеличении n вычитаемое ${\displaystyle {\frac {!n}{n!}}}$ стремится к ${\displaystyle \lim _{n\to \infty }{!n \over n!}=\lim _{n\to \infty }\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}}=e^{-1}\approx 0.36788\ldots .}$

Таким образом, ответ почти не зависит (при n≥5) от количества писем и конвертов и примерно равен константе ${\displaystyle 1-e^{-1}\approx 0{,}63212}$.

Ссылки

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