Утверждение (классическое). Обозначим через $D_n$ число перестановок множества $\{1,\dots ,n\}$, не имеющих ни одной фиксированной точки (дерранжменты). Тогда
1) Формула включений-исключений:
$$D_n=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!\sum _{k=0}^n\frac{(-1{)}^k}{k!}.$$
2) Рекуррентные соотношения:
$$D_n=(n-1)(D_{n-1}+D_{n-2})(n\ge 2),$$ $$D_n=n{D}_{n-1}+(-1{)}^n.$$
3) Асимптотика и округление:
$$\frac{D_n}{n!}\to e^{-1}\text{при}n\to \infty ,D_n\sim \frac{n!}{e},$$ и в частности $D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor$ (округление до ближайшего целого).
Краткие доказательства.
1) (Включения-исключения.) Для каждого множества $S$ из $k$ фиксированных точек число перестановок, фиксирующих по крайней мере все точки из $S$, равно $(n-k)!$. Применяя принцип включений-исключений по множествам фиксированных точек, получаем
$$D_n=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!.$$ Переписав $\left(\genfrac{}{}{0ex}{}{n}{k}\right)(n-k)!=n!/k!$, получаем вторую форму.
2) (Рекурсия.) Рассмотрим образ элемента $1$ в перестановке. Пусть $1$ переходит в $j\ne 1$. Рассмотрим два случая: либо $j$ переходит в $1$, либо нет.
- Если $j\mapsto 1$, то остаётся зде́сь переставить остальные $n-2$ элементов без фиксированных точек: даёт $D_{n-2}$ вариантов.
- Если $j/\mapsto 1$, то можно считать, что мы «связали» $1$ с $j$ и остаётся дерранжировать $n-1$ элементов так, чтобы $j$ не был фиксирован — даёт $D_{n-1}$ вариантов.
Так как выбор $j$ даёт $n-1$ вариантов, суммарно $D_n=(n-1)(D_{n-1}+D_{n-2})$. Вторая рекурсия следует алгебраически из формулы включений-исключений.
3) (Асимптика.) Из формулы
$$\frac{D_n}{n!}=\sum _{k=0}^n\frac{(-1{)}^k}{k!}$$ и сходимости степенного ряда ${\sum }_{k=0}^{\infty }(-1{)}^k/k!=e^{-1}$ следует $\frac{D_n}{n!}\to e^{-1}$. Отсюда $D_n\sim n!/e$. Оценка остатка для чередующегося ряда даёт ∣Dn−n!e∣<n!(n+1)!=1n+1≤12\bigl|D_n-\tfrac{n!}{e}\bigr|<\tfrac{n!}{(n+1)!}=\tfrac{1}{n+1}\le\tfrac12 Dn −en! <(n+1)!n! =n+11 ≤21 при $n\ge 1$, откуда утверждение об округлении.
Применение в анализе алгоритмов случайной перестановки.
- Вероятность того, что случайная равновероятная перестановка не имеет фиксированных точек, равна
$$\mathrm{Pr}(\text{нет фикс. точек})=\frac{D_n}{n!}\to e^{-1}\approx \mathrm{0.3679.}$$ Следствие: при генерации случайной перестановки и применении метода «генерируй и отвергай, пока не получишь дерранжмент» среднее число попыток стремится к $e$. То есть метод отвергания даёт ожидаемую константную сложность ~$e$ вызовов генератора перестановки.
- Число фиксированных точек в случайной перестановке равно сумме индикаторных случайных величин; его матожидание и дисперсия равны 1, и распределение сходится к распределению Пуассона с параметром 1:
$$\mathrm{Pr}(\text{ровно}k\text{фикс. точек})\to e^{-1}\frac{1}{k!}.$$ Это удобно при анализе алгоритмов, где «ошибки» или «совпадения» моделируются фиксированными точками: количество таких совпадений остаётся в среднем константным и подчиняется пределу Пуассона, что упрощает оценку вероятностей больших отклонений и ожидаемого поведения.
- Практический вывод: для задач, где требуется случайная перестановка без фиксированных точек (например, «Secret Santa», перестановки в криптографии, распределение задач без самоназначения), эффективные подходы: прямое построение дерранжмента (существуют линейные алгоритмы) или простое отвергание случайной перестановки с ожидаемым числом попыток $\approx e$.
Таким образом, знание формул и асимптотики для $D_n$ даёт точные вероятностные оценки и простые практические выводы для алгоритмов, работающих со случайными перестановками.