Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 did the author calculate 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*} $$

share|improve this question
    
    
Formula 1 here might be better, for purposes of proving the recursion. –  J. M. Nov 18 '11 at 14:26
    
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$. –  Did Nov 18 '11 at 16:16
2  
@Didier: It wasn't Piehead's fault. I'll fix it. –  J. M. Nov 18 '11 at 16:20
    
@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. –  Did Nov 18 '11 at 16:28

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
    
thanks a lot :) –  Piehead Nov 18 '11 at 16:17
    
@Piehead: May I suggest accepting robjohn's answer instead of mine? His covers a lot more than I did. –  J. M. Nov 19 '11 at 1:16

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

share|improve this answer
4  
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? –  Ian Aug 28 '12 at 15:12
    
@Ian: and in the estimate for $E_n$ that follows. Good eye! –  robjohn Aug 28 '12 at 15:41

Derangements:

A Derangement is a permutation in which no element is mapped to itself. 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 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} $$

share|improve this answer
2  
+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. –  Mike Spivey Nov 18 '11 at 22:07
1  
@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). –  robjohn Nov 18 '11 at 23:07
2  
I just wanted to point it out. My toes didn't feel stepped on. :) –  Mike Spivey Nov 18 '11 at 23:12
    
Nice. See also this question on finding the generating function for the derangements, which has some nice methods. –  ShreevatsaR Feb 27 at 5:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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