Abstract Nonsense

Number of Derangements

Point of post: In this post we will do a simple, but classic counting exercise to figure out how many derangements there are on $[n]$.

Motivation

A derangement of the set $[n]=\{1,\cdots,n\}$ is an element $\pi$ of $S_n$ (click the symbol if you’re unsure what it means) such that $\pi(x)\ne x$ for all $x\in[n]$. In this post we will prove, in two ways, how many derangements there are of $n$ objects. This is interesting combinatorially as it answers the question “Suppose that a class of students takes a quiz and the teacher collects them. How many ways can the teacher redistribute the quizzes for peer grading, with the obvious proviso that no student get’s his/her own paper?”  So, with this in mind, let’s begin.

Remark: I shall use $\text{card }$ and $|\cdot|$ interchangeably for cardinality throughout this post.

Theorem: Let $D_n$ be the set of derangements of $\{1,\cdots,n\}$. Then,

$\displaystyle \left|D_n\right|=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}$

Proof: Clearly we have that

$\displaystyle D_n=\bigcap_{j=1}^{n}\left\{f:[n]\to[n]:f(j)\ne j\right\}$

and thus

$\displaystyle D_n=[n]-\bigcup_{j=1}^{n}A_j$

where $A_j=\left\{f:[n]\to[n]:f(j)=j\right\}$, and thus

$\displaystyle \left|D_n\right|=S_n-\left|\bigcup_{j=1}^{n} A_j\right|$

Thus, by the inclusion-exclusion principle it follows that

$\displaystyle \left|D_n\right|=n!-\sum_{j=1}^{n}(-1)^{j+1}\sum_{S\in S_j}\left|\bigcap_{s\in S}A_s\right|$

where $S_j=\left\{S\subseteq [n]:|S|=j\right\}$. Note though that

$\displaystyle \bigcap_{s\in S}A_s=\left\{f:[n]\to[n]:f(s)=s\text{ for all }s\in S\right\}$

and evidently this is equipotent to $S_{n-j}$ and thus

$\displaystyle \left|\bigcap_{s\in S}\left|A_s\right|\right|=(n-j)!$

but, this was true for all $S\in S_j$. Thus,

$\displaystyle \left|D_n\right|=n!-\sum_{j=1}^{n}(-1)^{j+1}\sum_{S\in S_j}(n-j)!$

but, clearly since $\displaystyle \left|S_j\right|={n\choose j}$ it follows that

\displaystyle \begin{aligned}\left|D_n\right|&=n!-\sum_{j=1}^{n}(-1)^{j+1}{n\choose j}(n-j)!\\ &=n!\left[1+\sum_{j=1}^{n}\frac{(-1)^j}{j!}\right]\\ &= n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}\end{aligned}

as desired. $\blacksquare$

The second method uses techinques outlined in Herbert Wilf’s Generatingfunctionology

Proof: Let $a_n=\left|D_n\right|$ and let $G(x)$ be the generating function for $a_n$. Note that evidently the number of $f\in S_n$ with exactly $k$ fixed points is evidently $a_{n-k}$ from where it easily follows that

$\displaystyle S_n=\bigcup_{k=0}^{n}D_{n-k}$

so that

$\displaystyle n!=\sum_{k=0}^{\infty}{n\choose k}a_{n-k}$

taking the $\text{e.g.f.}$ (convoluting) of both sides gives that

$\displaystyle \frac{1}{1-x}=e^x G(x)$

so that

$\displaystyle \frac{e^{-x}}{1-x}=G(x)$

Thus, recalling that in general if $\left[x^n\right]f(x)=f_n$ then $\displaystyle \left[x^n\right]\frac{f(x)}{1-x}=\sum_{j=0}^{n}f_n$. And thus,

$\displaystyle \frac{a_n}{n!}=\left[x^n\right]\frac{e^{-x}}{1-x}=\sum_{j=0}^{n}\frac{(-1)^j}{j!}$

as required. $\blacksquare$

References:

1. Wilf, Herbert S. Generatingfunctionology. Boston: Academic, 1994. Print.