The derangement number $D_n$: the number of bijections of an $n$-element set with no fixed point

Let $A$ be a finite set. A derangement of $A$ is a bijection $f:A\to A$ with $f(a)\mathrm{\ne }a$ for every $a\in A$ (Injection, surjection, bijection). Write

$\mathrm{Der}(A):=\{f\in \mathrm{Bij}(A):f(a)\mathrm{\ne }a\text{ for every }a\in A\},$

where $\mathrm{Bij}(A)$ is the set of bijections of $A$ onto itself.

$\mathrm{Der}(A)$ is finite. $\mathrm{Bij}(A)$ is finite with $\mid \mathrm{Bij}(A)\mid =\mid A\mid !$ (A finite set $A$ with $\mid A\mid =n$ has exactly $n!$ bijections onto itself, and $n!$ bijections onto any set of the same cardinality, The factorial $n!$ and the falling factorial $n^{\underset{‾}{k}}$, defined by recursion in $\mathbb{N}$), and $\mathrm{Der}(A)$ is a subset of it, hence finite (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, clause 1). So $\mid \mathrm{Der}(A)\mid$ is a natural number (The cardinality $\mid A\mid$ of a finite set).

The count depends only on $\mid A\mid$. Let $h:A\to A^{\mathrm{\prime }}$ be a bijection of finite sets. The map $f\mapsto h\circ f\circ h^{-1}$ sends $\mathrm{Bij}(A)$ into $\mathrm{Bij}(A^{\mathrm{\prime }})$, since composites and inverses of bijections are bijections, and it sends $\mathrm{Der}(A)$ into $\mathrm{Der}(A^{\mathrm{\prime }})$: if $h(f(h^{-1}(a^{\mathrm{\prime }})))=a^{\mathrm{\prime }}$ for some $a^{\mathrm{\prime }}\in A^{\mathrm{\prime }}$ then, applying $h^{-1}$ and writing $a:=h^{-1}(a^{\mathrm{\prime }})$, we get $f(a)=a$. The map $g\mapsto h^{-1}\circ g\circ h$ is a two-sided inverse, so $\mathrm{Der}(A)\approx \mathrm{Der}(A^{\mathrm{\prime }})$ and the two sets have the same cardinality by the transport clause (c) of The cardinality $\mid A\mid$ of a finite set.

Definition. For $n\in \mathbb{N}$ (The natural numbers $\mathbb{N}$ (von Neumann)) set

$D_n:=\mid \mathrm{Der}(n)\mid \in \mathbb{N},$

the derangement number. Since $\mid n\mid =n$, the previous paragraph gives $\mid \mathrm{Der}(A)\mid =D_{\mid A\mid }$ for every finite set $A$.

Three values, read off the definition and not stipulated.

• $D_0=1$. Here $0=\mathrm{\varnothing }$, the only function $\mathrm{\varnothing }\to \mathrm{\varnothing }$ is the empty function, it is a bijection, and the condition "$f(a)\mathrm{\ne }a$ for every $a\in \mathrm{\varnothing }$" holds vacuously. So $\mathrm{Der}(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$.
• $D_1=0$. Here $1=\{0\}$ and the only bijection of $\{0\}$ is the identity, which fixes $0$.
• $D_2=1$. Here $2=\{0,1\}$, the two bijections are the identity and the exchange of $0$ and $1$, and only the second is fixed-point free.

• A set of bijections, with no group vocabulary. The object counted is a set of functions. Nothing among this page's declared prerequisites defines a symmetric group, a permutation cycle or a conjugacy class, and no result about $D_n$ stated here needs one.

• $D_0=1$ is not a convention. It is what the definition returns at $n=0$, and it is the value that makes the closed formula and the first recurrence true at their first legal index. A text that sets $D_0=1$ "by convention" is stipulating what is here computed.