1) Обозначим через

количество перестановок длины

, в которых все циклы имеют чётную длину. Тогда
(

--- количество способов выбрать цикл длины

, содержащий

). Поэтому, если обозначить

, то
т.е.

.
Аналогично, если обозначить через

количество перестановок длины

, в которых все циклы имеют нечётную длину, то
т.е.

удовлетворяет
т.е.

, поэтому
По пути сосчитали искомое количество перестановок

.