Problem
COM-B2-M02-P020 No Fixed Points and No Transpositions
Derive a formula for the number of permutations of \(n\) elements with no fixed points and no cycles of length \(2\).
Choose \(i\) fixed points and \(j\) disjoint transpositions, then permute the remaining elements.
Apply inclusion-exclusion to the forbidden events: “an element is fixed” and “a pair forms a transposition”. If \(i\) fixed elements and \(j\) disjoint transpositions are chosen, the forbidden structure can be chosen in \(\frac{n!}{i!\,j!\,2^j\,(n-i-2j)!}\) ways. The remaining \(n-i-2j\) elements are permuted freely in \((n-i-2j)!\) ways. The sign is \((-1)^{i+j}\). Hence the number is
\[\sum_{\substack{i,j\ge0\\ i+2j\le n}}(-1)^{i+j}\frac{n!}{i!\,j!\,2^j}.\]
A strong problem: inclusion-exclusion runs over two types of forbidden events.