Paper 4, Section II, E

Numbers and Sets | Part IA, 2015

State the inclusion-exclusion principle.

Let nNn \in \mathbb{N}. A permutation σ\sigma of the set {1,2,3,,n}\{1,2,3, \ldots, n\} is said to contain a transposition if there exist i,ji, j with 1i<jn1 \leqslant i<j \leqslant n such that σ(i)=j\sigma(i)=j and σ(j)=i\sigma(j)=i. Derive a formula for the number, f(n)f(n), of permutations which do not contain a transposition, and show that

limnf(n)n!=e12\lim _{n \rightarrow \infty} \frac{f(n)}{n !}=e^{-\frac{1}{2}}

Typos? Please submit corrections to this page on GitHub.