Задача
COM-B2-M02-P020 Без неподвижных точек и без транспозиций
Выведите формулу для числа перестановок \(n\) элементов, в которых нет неподвижных точек и нет циклов длины \(2\).
Выберите \(i\) неподвижных точек и \(j\) непересекающихся транспозиций, затем переставьте остальные элементы.
Применим включения-исключения к запрещённым событиям: “элемент фиксирован” и “пара образует транспозицию”. Если выбраны \(i\) фиксированных элементов и \(j\) непересекающихся транспозиций, то сначала выбираем эти элементы и пары: \(\frac{n!}{i!\,j!\,2^j\,(n-i-2j)!}\) способов для структуры запретов. Остальные \(n-i-2j\) элементов переставляются произвольно: \((n-i-2j)!\) способов. Вклад имеет знак \((-1)^{i+j}\). Поэтому число равно
\[\sum_{\substack{i,j\ge0\\ i+2j\le n}}(-1)^{i+j}\frac{n!}{i!\,j!\,2^j}.\]
Сильная задача: здесь включения-исключения идёт по двум типам запретов.