= Solution
For a finite family of subsets $A_1,\ldots,A_N$ of a finite set $\Omega$, the <inclusion-exclusion principle> states
$$
\left|\bigcup_{i=1}^N A_i\right|=\sum_{\varnothing\ne J\subseteq\{1,\ldots,N\}}(-1)^{|J|+1}\left|\bigcap_{j\in J}A_j\right|.
$$
Let $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>:
$$
\boxed{f(n)=\sum_{r=0}^{\lfloor n/2\rfloor}(-1)^r\frac{n!}{2^rr!}.}
$$
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
$$
\boxed{\lim_{n\to\infty}\frac{f(n)}{n!}=\sum_{r=0}^{\infty}\frac{(-1/2)^r}{r!}=e^{-1/2}.}
$$
Back to article page
