 Solution

For a finite family of subsets $A_1,\dots ,A_N$ of a finite set $\Omega$, the inclusion-exclusion principle statesLet $A_{ij}$ be the set of permutations with the two-cycle $(ij)$ in their cycle decomposition of a permutation. Two distinct specified pairs sharing a label cannot both occur, so their intersection is empty. An intersection containing $r$ pairwise disjoint specified pairs fixes those $2r$ labels and leaves $(n-2r)!$ choices for the other labels.

The number of ways to choose $r$ disjoint unordered pairs is $n!/[2^{r}r!(n-2r)!]$: first order the selected labels, then divide by the two orders within each pair, by the $r!$ orders of the pairs, and by the orders of the unused labels. Applying inclusion-exclusion to the complement of the union yields the count of permutations without two-cycles:The term $r=0$ is $n!$. Fixed points and cycles of length at least three are allowed; the restriction concerns two-cycles, not whether a permutation can be expressed as a product of transpositions.

Dividing by $n!$ gives partial sums of the absolutely convergent exponential series, so