I have a problem understanding the proof of Rencontres numbers (Derangements)

Question

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation

$$D_{n,0}=\left[\frac{n!}{e}\right]$$

where $[\cdot]$ denotes the rounding function (i.e., $[x]$ is the integer nearest to $x$). This equation that I wrote comes from solving the following recursion, but I don't understand how exactly the author calculated this recursion.

$$\begin {align*} D_{n+2,0} & =(n+1)(D_{n+1,0}+D_{n,0}) \\ D_{0,0} & = 1 \\ D_{1,0} & = 0 \end {align*} $$

Answer 1

(This argument is adapted from page 195 of Concrete Mathematics, Second Edition)

We start with the more conventional representation for the Rencontres number (subfactorial):

$$D_{n,0}=!n=n!\sum_{k=0}^n \frac{(-1)^k}{k!}$$

We also know that

$$\frac{n!}{e}=n!\sum_{k=0}^\infty \frac{(-1)^k}{k!}$$

The difference is

$$\begin{align*}\frac{n!}{e}-!n&=n!\sum_{k=n+1}^\infty \frac{(-1)^k}{k!}\\&=\frac{(-1)^{n+1}}{n+1}\left(1-\frac1{n+2}+\frac1{(n+2)(n+3)}-\cdots\right)\end{align*}$$

and since

$$\frac1{n+2} \leq \left|\frac{n!}{e}-!n\right| \leq \frac1{n+1}$$

along with knowing that $!n$ is an integer, rounding $n!/e$ to the nearest integer gives the subfactorial.

---

We have

$\small \begin{align}(n+2)!\sum_{k=0}^{n+2} \frac{(-1)^k}{k!}&=(n+1)\left[(n+1)!\sum_{k=0}^{n+1} \frac{(-1)^k}{k!}+n!\sum_{k=0}^n \frac{(-1)^k}{k!}\right]\\(n+2)(n+1)\sum_{k=0}^{n+2} \frac{(-1)^k}{k!}&=(n+1)\left[(n+1)\sum_{k=0}^{n+1} \frac{(-1)^k}{k!}+\sum_{k=0}^n \frac{(-1)^k}{k!}\right]\\(n+2)\sum_{k=0}^{n+2} \frac{(-1)^k}{k!}&=(n+1)\sum_{k=0}^{n+1} \frac{(-1)^k}{k!}+\sum_{k=0}^n \frac{(-1)^k}{k!}\\(n+2)\left(\frac{(-1)^{n+2}}{(n+2)!}+\frac{(-1)^{n+1}}{(n+1)!}+\sum_{k=0}^n \frac{(-1)^k}{k!}\right)&=\frac{(-1)^{n+1}}{n!}+(n+1)\sum_{k=0}^n \frac{(-1)^k}{k!}+\sum_{k=0}^n \frac{(-1)^k}{k!}\\(n+2)\left(\frac{(-1)^n}{(n+2)!}+\frac{(-1)^{n+1}}{(n+1)!}\right)+(n+2)\sum_{k=0}^n \frac{(-1)^k}{k!}&=\frac{(-1)^{n+1}}{n!}+(n+1)\sum_{k=0}^n \frac{(-1)^k}{k!}+\sum_{k=0}^n \frac{(-1)^k}{k!}\\(n+2)\left(\frac{(-1)^n}{(n+2)!}+\frac{(-1)^{n+1}}{(n+1)!}\right)&=\frac{(-1)^{n+1}}{n!}\\(-1)^n+(-1)^{n+1}(n+2)&=(-1)^{n+1}(n+1)\\1-(n+2)&=-(n+1)\end{align}$

and the last bit is easily established, thus proving the recursion relation for the Rencontres numbers.

Answer 2

Derangements:

A Derangement is a permutation, $P$, in which no element is mapped to itself; that is, $P(k)\ne k$, for $1\le k\le n$. Let $\mathcal{D}(n)$ be the number of derangements of $n$ items.

Here are a few methods of computing $\mathcal{D}(n)$.

Method 1 (build from smaller derangements):

Let us count the number of derangements of $n$ items so that $P(P(n))=n$. There are $n-1$ choices for $P(n)$, and for each of those choices, $\mathcal{D}(n-2)$ ways to arrange the other $n-2$ items. Thus, there are $(n-1)\mathcal{D}(n-2)$ derangements of $n$ items so that $P(P(n))=n$.

Let us count the number of derangements of $n$ items so that $P(P(n))\not=n$. There are $n-1$ choices for $P(n)$, and for each choice, there is a derangement of $n-1$ items identical to $P$ except that they map $P^{-1}(n)\to P(n)$. Thus, there are $(n-1)\mathcal{D}(n-1)$ derangements of $n$ items so that $P(P(n))\not=n$.

Therefore, $$ \mathcal{D}(n)=(n-1)(\mathcal{D}(n-1)+\mathcal{D}(n-2))\tag{1} $$ Method 2 (count permutations):

Count the number of permutations of $n$ items by counting how many fix exactly $k$ items.

There are $\binom{n}{k}$ ways to choose the $k$ items to fix, then $\mathcal{D}(n-k)$ ways to arrange the $n-k$ items that are not fixed. Since there are $n!$ permutations of $n$ items, we get $$ n!=\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)\tag{2} $$ and therefore, rearranging $(2)$ yields $$ \mathcal{D}(n)=n!-\sum_{k=1}^n\binom{n}{k}\mathcal{D}(n-k)\tag{3} $$ Method 3 (inclusion-exclusion):

Let $S_i$ be the set of permutations of $n$ items which fix item $i$. Then the number of permutations in $k$ of the $S_i$ would be the number of permutations that fix $k$ items. There are $\binom{n}{k}$ ways to choose the $k$ items to fix, and $(n-k)!$ ways to arrange the other $n-k$ items. Thus, the number of permutations that fix at least $1$ item would be $$ \sum_{k=1}^n(-1)^{k-1}\binom{n}{k}(n-k)!=\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\tag{4} $$ Since there are $n!$ permutations in total, the number of permutations that don't fix any items is $$ \begin{align} \mathcal{D}(n) &=n!-\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\\ &=\sum_{k=0}^n(-1)^k\frac{n!}{k!}\tag{5}\\ &\approx \frac{n!}{e} \end{align} $$ In fact, the difference $$ \begin{align} \left|\frac{n!}{e}-\mathcal{D}(n)\right| &=\left|\sum_{k=n+1}^\infty(-1)^k\frac{n!}{k!}\right|\\ &=\left|\frac{1}{n+1}-\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}-\dots\right|\\ &<\frac{1}{n+1}\tag{6} \end{align} $$ This method yields directly that $\mathcal{D}(n)$ is the closest integer to $\frac{n!}{e}$ for $n>0$.

Derivation of the Closed Form from the Recursion:

Given $\mathcal{D}(0)=1$ and $\mathcal{D}(1)=0$, and the recursion $(1)$, let's derive $(5)$. Subtracting $n\mathcal{D}(n-1)$ from both sides of $(1)$ yields $$ \mathcal{D}(n)-n\mathcal{D}(n-1)=-(\mathcal{D}(n-1)-(n-1)\mathcal{D}(n-2))\tag{7} $$ Using the initial conditions, $(7)$ implies $$ \mathcal{D}(n)-n\mathcal{D}(n-1)=(-1)^n\tag{8} $$ Dividing both sides of $(8)$ by $n!$ yields $$ \frac{\mathcal{D}(n)}{n!}-\frac{\mathcal{D}(n-1)}{(n-1)!}=\frac{(-1)^n}{n!}\tag{9} $$ Equation $(9)$ is very simple to solve for $\frac{\mathcal{D}(n)}{n!}$: $$ \frac{\mathcal{D}(n)}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}+C\tag{10} $$ Plugging $n=0$ into equation $(10)$ yields that $C=0$. Therefore, $$ \mathcal{D}(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\tag{11} $$

Answer 3

Here's a different derivation. A derangement $D_n$ ($= D_{n,0}$) is a permutation of $n$ elements with no fixed points. We will prove an integral representation for $D_n$ that produces quick derivations of $D_n \approx n!/e$ and $D_n = n! \sum_{k=0}^n (-1)^k/k!.$

A combinatorial proof of the recurrence for $D_n$:

Here's a combinatorial proof of $D_n = (n-1)(D_{n-1} + D_{n-2})$ for $n \geq 2$ due to Euler.

For any derangement $(j_1, j_2, \ldots, j_n)$, we have $j_n \neq n$. Let $j_n = k$, where $k \in \{1, 2, \ldots, n-1\}$. We now break the derangements on $n$ elements into two cases.

Case 1: $j_k = n$ (so $k$ and $n$ map to each other). By removing elements $k$ and $n$ from the permutation we have a derangement on $n-2$ elements, and so, for fixed $k$, there are $D_{n-2}$ derangements in this case.

Case 2: $j_k \neq n$. Swap the values of $j_k$ and $j_n$, so that we have a new permutation with $j_k = k$ and $j_n \neq n$. By removing element $k$ we have a derangement on $n-1$ elements, and so, for fixed $k$, there are $D_{n-1}$ derangements in this case.

Thus, with $n-1$ choices for $k$, we have, for $n \geq 2$, $$D_n = (n-1)(D_{n-1} + D_{n-2}). \tag{1}$$

An integral representation for $D_n$:

It turns out that $$D_n = \int_0^{\infty} (t-1)^n e^{-t} dt. \tag{2}$$

(The similarity of $(2)$ with the integral representation for the factorial as a gamma function is perhaps another reason it makes sense to call the derangements the "subfactorials.")

We will prove $(2)$ by showing that the integral satisfies $(1)$. Let $R_n = \int_0^{\infty} (t-1)^n e^{-t} dt$.

Applying integration by parts yields $$R_n = (-1)^n + n R_{n-1} , \tag{3}$$ which is the recurrence $(8)$ in robjohn's answer. Applying the recurrence $(3)$ again with $R_{n-1}$ yields $$ \begin{align} R_n &= (-1)^n + (n-1)R_{n-1} + R_{n-1} \\ &= (-1)^n + (n-1)R_{n-1} + (-1)^{n-1} + (n-1)R_{n-2} \\ & = (n-1)(R_{n-1} + R_{n-2}). \end{align} $$ Since $R_0 = 1 = D_0$ and $R_1 = 0 = D_1$, Equation $(2)$ is established.

Equation $(2)$ is actually a special case of a more general result that says that the number of permutations with a specified set of fixed points can be represented by $\int_0^{\infty} R_{\tilde{G}}(t) e^{-t} dt$, where $\tilde{G}$ is the complement of $G$ in the complete bipartite graph on $n$ elements, and $R_G(t)$ is the associated rook polynomial for $G$. (See, for example, P. Mark Kayll, "Integrals Don't Have Anything to Do with Discrete Math, Do They?", Mathematics Magazine 84(2): 2011, 108-119.)

The approximation for $D_n$:

From $(2)$ we have $$ \begin{align} D_n &= \int_0^{\infty} (t-1)^n e^{-t} dt \\ &= \int_1^{\infty} (t-1)^n e^{-t} dt + \int_0^1 (t-1)^n e^{-t} dt \\ &= e^{-1} \int_0^{\infty} x^n e^{-x} dx + E_n \\ &= e^{-1} \Gamma(n+1) + E_n \\ &= \frac{n!}{e} + E_n. \end{align} $$ The quantity $E_n$ is small, too: $$|E_n| < \left|\int_0^1 (t-1)^n dt \right| = \frac{1}{n+1},$$ so that $$D_n \approx \frac{n!}{e}.$$

The explicit formula for $D_n$:

Again from $(2)$ we have $$ \begin{align} D_n &= \int_0^{\infty} (t-1)^n e^{-t} dt \\ &= \int_0^{\infty} \sum_{k=0}^n \binom{n}{k} (-1)^k t^{n-k} e^{-t} dt \\ &= \sum_{k=0}^n \binom{n}{k} (-1)^k \int_0^{\infty} t^{n-k} e^{-t} dt \\ &= n! \sum_{k=0}^n \frac{(-1)^k}{k! (n-k)!} \Gamma(n-k+1) \\ &= n! \sum_{k=0}^n \frac{(-1)^k}{k!}. \end{align} $$

(I learned these arguments from the Kayll paper referenced above.)