Дерегации — это перестановки (n) элементов без фиксированных точек. Обозначим их число (D_n).

1) Формула через включение‑исключение (вывод коротко):

Число перестановок, фиксирующих ровно (k) заданных точек, равно (\binom{n}{k}(n-k)!).По включению‑исключению
[
Dn=\sum{k=0}^n (-1)^k\binom{n}{k}(n-k)! = n!\sum_{k=0}^n\frac{(-1)^k}{k!}.
]

2) Рекуррентные формулы и их вывод (комбинаторный):

Начальные условия: (D_0=1,\;D_1=0).Основная рекурсия (разбиение по тому, куда попадает образ элемента 1):
[
Dn=(n-1)\bigl(D{n-1}+D{n-2}\bigr)\quad (n\ge2).
]
Краткое объяснение: выбрали образ 1 в одном из (n-1) мест; либо туда ставим элемент, который раньше шёл на 1 (получая циклы длины 2) — даёт множитель (D{n-2}), либо нет — даёт (D_{n-1}).Альтернативная форма (следствие включения‑исключения):
[
Dn=nD{n-1}+(-1)^n.
]

3) Асимптотика и приближение:
[
D_n\sim\frac{n!}{e},\qquad D_n=\Big\lfloor\frac{n!}{e}+\tfrac12\Big\rfloor.
]

4) Сравнение методов — когда что лучше

Включение‑исключение:
Плюсы: компактная теоретическая формула, хороша для доказательств, получения асимптотики и для аналитических преобразований.Минусы: при численном расчёте требует суммирования знакопеременных членов или работы с факториалами — потенциальные проблемы с точностью при плавающей арифметике; для больших (n) удобнее работать с целыми арифметикой или использовать приближение.Рекуррентные формулы:
Плюсы: простая и эффективная реализация в программировании (динамическое программирование), линейное время (O(n)) и стабильность при целочисленных вычислениях (умножение/сложение больших целых).Минусы: даёт менее «замкнутую» форму, менее очевидна для аналитики.Практические рекомендации:
Для теоретических выводов, доказательств и получения асимптотики — включение‑исключение.Для вычисления точных значений при больших (n) — рекурсия (работать с большими целыми).Для приближённых значений при очень больших (n) — использовать (n!/e) и округление.

Небольшие значения: (D_0=1,\;D_1=0,\;D_2=1,\;D_3=2,\;D_4=9,\dots).