Задача
COM-B2-M02-P009 Формула беспорядков
#9
★★★☆☆ Уровень 3 из 5
Докажите, что число перестановок \(n\) элементов без неподвижных точек равно \(D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}\).
Пусть \(A_i\) — событие “элемент \(i\) неподвижен”.
Если выбраны \(i\) элементов, которые должны быть неподвижны, то остальные \(n-i\) элементов можно переставить \((n-i)!\) способами. По включениям-исключениям
\[D_n=\sum_{i=0}^n(-1)^i\binom ni(n-i)!=n!\sum_{i=0}^n\frac{(-1)^i}{i!}.\]
Ключевая формула модуля.