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


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*} $$

  • $\begingroup$ en.wikipedia.org/wiki/Rencontres_numbers $\endgroup$
    – Piehead
    Nov 18 '11 at 14:15
  • 1
    $\begingroup$ Formula 1 here might be better, for purposes of proving the recursion. $\endgroup$ Nov 18 '11 at 14:26
  • $\begingroup$ If the floor function is the function which sends any real number $x$ to the largest integer not greater than $x$, as is customary, the assertion is false, for even values of $n$. For example there is $1$ derangement of $\{1,2\}$ but $\lfloor2!/e\rfloor=0$. $\endgroup$
    – Did
    Nov 18 '11 at 16:16
  • 2
    $\begingroup$ @Didier: It wasn't Piehead's fault. I'll fix it. $\endgroup$ Nov 18 '11 at 16:20
  • $\begingroup$ @J.M. I had not looked at the original version of the post (which properly refers to the rounding function) when I wrote the preceding comment. $\endgroup$
    – Did
    Nov 18 '11 at 16:28

(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.

  • 2
    $\begingroup$ @Piehead: May I suggest accepting robjohn's answer instead of mine? His covers a lot more than I did. $\endgroup$ Nov 19 '11 at 1:16


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} $$

  • 5
    $\begingroup$ +1 for the nice survey on derangements. Two comments: 1) Your Method 1 is equivalent to my answer. 2) You might be interested in this paper of mine generalizing the derangement numbers. $\endgroup$ Nov 18 '11 at 22:07
  • 1
    $\begingroup$ @Mike: I didn't mean to step on any toes. However, I wanted to include $(1)$ because I was planning on using it to derive the closed form (I've just added said derivation). $\endgroup$
    – robjohn
    Nov 18 '11 at 23:07
  • 2
    $\begingroup$ I just wanted to point it out. My toes didn't feel stepped on. :) $\endgroup$ Nov 18 '11 at 23:12
  • 1
    $\begingroup$ @user350331: Inclusion-Exclusion says that the number of items in the union is $$\sum_{k=1}^n(-1)^{k-1}N(k)$$ where $N(k)$ is the sum of the number of items in all of the intersections of $k$ of the $S_i$. To count these, we multiply the number of intersections of $k$ of the $S_i$, $\binom{n}{k}$, by the size of each intersection of $k$ of the $S_i$, $(n-k)!$. $\endgroup$
    – robjohn
    Dec 17 '16 at 9:59
  • 1
    $\begingroup$ @Miokloń: It's proven in $(6)$, which is mainly an application of the Alternating Series Test. $\endgroup$
    – robjohn
    Nov 28 '17 at 2:05

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.)

  • 4
    $\begingroup$ A yearish late, but in the second step of the approximation of D_n, shouldn't the latter integral run from 0 to 1 instead of 0 to \infty? $\endgroup$
    – Ian Eccles
    Aug 28 '12 at 15:12
  • $\begingroup$ @Ian: and in the estimate for $E_n$ that follows. Good eye! $\endgroup$
    – robjohn
    Aug 28 '12 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.