# Number of derangements of n objects

• Feb 9th 2010, 01:54 PM
Bruno J.
Number of derangements of n objects
Recall that a derangement of a set $\displaystyle S$ is a permutation $\displaystyle \pi$ of $\displaystyle S$ having no fixed points, i.e. $\displaystyle \pi(s)\neq s \ \ \forall s \in S$. If the number of derangements of $\displaystyle \{1,\dots,n\}$ is $\displaystyle !n$, show that

$\displaystyle !n = \sum_{j=0}^n{n \choose j}(-1)^{n-j} j!$.

Hint :

Spoiler:
You might first want to show that if $\displaystyle b_n$ is an arbitrary sequence and $\displaystyle a_n=\sum_{j=0}^n{n\choose j}b_j$, then $\displaystyle b_n$ can be retrieved by $\displaystyle b_n = \sum_{j=0}^n{n\choose j}(-1)^{n-j}a_j$.

• Feb 9th 2010, 02:02 PM
wonderboy1953
Question
Is $\displaystyle n!$ the same as $\displaystyle !n$?
• Feb 9th 2010, 02:03 PM
Bruno J.
No! $\displaystyle n!$ is the factorial and $\displaystyle !n$ is the number of derangements of a set having $\displaystyle n$ elements.
• Feb 9th 2010, 02:15 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Recall that a derangement of a set $\displaystyle S$ is a permutation $\displaystyle \pi$ of $\displaystyle S$ having no fixed points, i.e. $\displaystyle \pi(s)\neq s \ \ \forall s \in S$. If the number of derangements of $\displaystyle \{1,\dots,n\}$ is $\displaystyle !n$, show that

$\displaystyle !n = \sum_{j=0}^n{n \choose j}(-1)^j j!$.

Hint :

Spoiler:
You might first want to show that if $\displaystyle b_n$ is an arbitrary sequence and $\displaystyle a_n=\sum_{j=0}^n{n\choose j}b_j$, then $\displaystyle b_n$ can be retrieved by $\displaystyle b_n = \sum_{j=0}^n{n\choose j}(-1)^ja_j$.

A well-worded argument with the inclusion-exclusion principle shows that $\displaystyle !n=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}$. But $\displaystyle \sum_{j=0}^{n}{n\choose j}(-1)^j j!$. Applying the symmetry of the sum finishes the argument. I suppose you want me to show that inclusion-exclusion argument?
• Feb 9th 2010, 02:19 PM
Bruno J.
Haha... well yeah, that would certainly complete your proof! (Giggle)
• Feb 9th 2010, 02:30 PM
Plato
Quote:

Originally Posted by Bruno J.
Recall that a derangement of a set $\displaystyle S$ is a permutation $\displaystyle \pi$ of $\displaystyle S$ having no fixed points, i.e. $\displaystyle \pi(s)\neq s \ \ \forall s \in S$. If the number of derangements of $\displaystyle \{1,\dots,n\}$ is $\displaystyle !n$, show that

[CENTER] $\displaystyle !n = \sum_{j=0}^n{n \choose j}(-1)^j j!$.

Bruno J
You need to adjust this form. For odd n it gives a negative of the correct answer.
$\displaystyle n=3$ gives $\displaystyle 1-3\cdot 1!+ 3\cdot 2! -3!=-2$
• Feb 9th 2010, 02:30 PM
Drexel28
Quote:

Originally Posted by Bruno J.
Haha... well yeah, that would certainly complete your proof! (Giggle)

I'll post one up later, if anyone else doesn't. Also, you can solve this with recurrence relations.
• Feb 9th 2010, 02:48 PM
Bruno J.
Quote:

Originally Posted by Plato
Bruno J
You need to adjust this form. For odd n it gives a negative of the correct answer.
$\displaystyle n=3$ gives $\displaystyle 1-3\cdot 1!+ 3\cdot 2! -3!=-2$

Quite right! I made a mistake. I have corrected it. Thank you Plato!
• Feb 9th 2010, 09:02 PM
Black
Spoiler:
For $\displaystyle j=1,2,\dots,n,$ let

$\displaystyle A_j=\{\sigma \in S_n|\, \sigma(j)=j\}.$

Then

$\displaystyle !n = n!-\left|\bigcup_{j=1}^nA_j\right|$.

By the inclusion-exclusion principle

$\displaystyle \left|\bigcup_{j=1}^nA_j\right|=\sum_{j=1}^{n}|A_i |-\sum_{1\le j<k \le n} |A_j \cap A_k|+ \cdots +(-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n|.$

Consider the intersection

$\displaystyle A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_r}=\{\sigma \in S_n|\, \sigma(j_1)=j_1, \sigma(j_2)=j_2, \dots ,\sigma(j_r)=j_r\}$, for $\displaystyle 1 \le r \le n.$

There are $\displaystyle \binom{n}{r}$ of these r-intersections, each of them having $\displaystyle (n-r)!$ permutations. Thus, we have

$\displaystyle \sum_{1 \le j_{1} < j_{2} < \cdots < j_{r} \le n}|A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_r}|=\binom{n}{r}(n-r)!$,

so

$\displaystyle !n = \binom{n}{0}n! -\left[\binom{n}{1}(n-1)!-\cdots +(-1)^{n-1}\binom{n}{n}(n-n)!\right]$

$\displaystyle =\binom{n}{n}(-1)^{n-n}n!+\binom{n}{n-1}(-1)^{n-(n-1)}(n-1)!+\cdots+\binom{n}{0}(-1)^n0!$

$\displaystyle =\sum_{j=0}^{n}\binom{n}{j}(-1)^{n-j}j!$.
• Feb 10th 2010, 07:18 AM
Bruno J.
Good job, Black! You are an impressive new member. (Bow) Are you a university student?

I will post another nice solution later today.
• Feb 10th 2010, 08:16 AM
Bruno J.
Here is another proof.

First, I prove the statement in the hint that I gave. Consider the exponential generating function

$\displaystyle g_B(z)=\sum_{j=0}^\infty b_j \frac{z^j}{j!}$

of the sequence $\displaystyle B=\{b_j\}$. By the basic properties of exponential generating functions, the product of the exponential generating functions of two sequences is the exponential generating function of their binomial convolution. So we have

$\displaystyle g_A(z) = \sum_{j=0}^\infty a_j \frac{z^j}{j!} = e^zg_B(z)$

and so $\displaystyle g_B(z)=e^{-z}g_A(z)$. Extracting the coefficient of $\displaystyle \frac{z^n}{n!}$ on both sides we obtain $\displaystyle b_n = \sum_{j=0}^n {n \choose j}(-1)^{n-j}a_j$ as required.

Now let us partition the set $\displaystyle S_n$ of permutations of $\displaystyle \{1,\dots,n\}$ as follows; let $\displaystyle T_j \subset S_n$ denote those permutations which have precisely $\displaystyle j$ fixed points, for $\displaystyle j=0, \dots, n$. Clearly there are $\displaystyle {n \choose j}$ ways of picking the elements which are to be fixed, and the remaining $\displaystyle n-j$ elements have to be deranged. So $\displaystyle |T_j| = {n \choose j}!(n-j)$. Since the $\displaystyle T_j$ are clearly distinct we have

$\displaystyle |S_n|=n!=\sum_{j=0}^n|T_j| = \sum_{j=0}^n{n \choose j}!(n-j) = \sum_{j=0}^n{n \choose j}!j$

because $\displaystyle {n \choose j} = {n \choose n-j}$. Now just apply the binomial involution just proved!