# Number of bijections with no fixed points

To test my new blog with MathJax integration, I'll post an old exercise proving that the number of bijections $f:A\to A$ with no fixed points equals $!n$. To be more precise, let $A$ be a finite set with $n$ elements. Then let $X=\{f:A\to A:f \ \text{is bijective and for all} \ m\in A, f(m)\neq m\}.$ Now $\left|X\right|=!n=n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$ I will prove this statement for $A'=\{1,\dots,n\}$, which clearly shares the same cardinality as $A$. Let $Y_m=\{f:A'\to A':f \ \text{is bijective and} \ f(m)=m\}$ and $Y=\bigcup\limits_{m \in A'} Y_m$. Since $X \cap Y=\varnothing$, by the principle of addition, $\left|X \cup Y\right|=\left|X\right|+\left|Y\right|.$ Now $\left|X \cup Y\right|=n!$ as it represents the set of all bijections $f:A'\to A'$. By the inclusion-exclusion principle, $\left|Y\right|=\left|\bigcup\limits_{m \in A'} Y_m\right|=\sum_{k\in \{1,\dots,n\}} (-1)^{k-1} \Sigma_k=\sum_{k=1}^n (-1)^{k-1} \Sigma_k$ where $\Sigma_k=\sum_{B \in \mathcal{P}_k\left(\{1,\dots,n\}\right)} \left| \bigcap_{i \in B} Y_i\right|.$ Once again using the number of bijections a set has we have that $\left| \bigcap_{i \in B} Y_i\right|=\left| \bigcap_{i \in \{1,\dots,k\}} Y_i\right|=(n-k)!.$ Thus $\Sigma_k=\sum_{B \in \mathcal{P}_k\left(\{1,\dots,n\}\right)} (n-k)!=\binom{n}{k}(n-k)!=\frac{n!}{k!},$ because $\left|\mathcal{P}_k(\{1,\dots,n\})\right|=\binom{n}{k}$ by definition. It then follows that $\left|Y\right|=\sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!}$ and thus \begin{aligned} \left|X\right|&=\left|X \cup Y\right|-\left|Y\right| \\ &=n!-\sum_{k=1}^n (-1)^{k-1} \frac{n!}{k!} \\ &=n!\left(1-\sum_{k=1}^n \frac{(-1)^{k-1}}{k!}\right) \\ &=n! \sum_{k=0}^n \frac{(-1)^k}{k!}. \end{aligned} As I mentioned in the beginning, this was an exercise for an introductory course to discrete mathematics. The inclusion-exclusion principle, which was at the time the subject of the week, unsurprisingly does most of the heavy lifting in this proof.

• Created:
January 3, 2020 17:32
• Updated:
January 3, 2020 19:37