Беспорядки (Derangements)

Перестановки где ни один элемент не остаётся на своём месте: !n = n!·Σ((-1)^k/k!) для k=0..n ≈ n!/e (при больших n). Рекуррентность: !n = (n-1)·(!(n-1) + !(n-2)), базовые !0=1, !1=0, !2=1, !3=2, !4=9. Вероятность случайной перестановки быть беспорядком: !n/n! → 1/e ≈ 0.368 (не зависит от n при n→∞). Задача: n человек сдали шляпы, получают случайную — вероятность что никто не получит свою = 1/e. Применение: теория вероятностей, задачи о назначениях