Number of derangements of n objects

**Bruno J.** · February 9th 2010, 01:54 PM

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

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

Hint :

Spoiler:

**wonderboy1953** · February 9th 2010, 02:02 PM

Is $n!$ the same as $!n$ ?

**Bruno J.** · February 9th 2010, 02:03 PM

No! $n!$ is the factorial and $!n$ is the number of derangements of a set having $n$ elements.

**Drexel28** · February 9th 2010, 02:15 PM

Originally Posted by Bruno J.

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

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

Hint :

Spoiler:

A well-worded argument with the inclusion-exclusion principle shows that $!n=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}$ . But $\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?

**Bruno J.** · February 9th 2010, 02:19 PM

Haha... well yeah, that would certainly complete your proof!

**Plato** · February 9th 2010, 02:30 PM

Originally Posted by Bruno J.

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

[CENTER] $!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.
$n=3$ gives $1-3\cdot 1!+ 3\cdot 2! -3!=-2$

**Drexel28** · February 9th 2010, 02:30 PM

Originally Posted by Bruno J.

Haha... well yeah, that would certainly complete your proof!

I'll post one up later, if anyone else doesn't. Also, you can solve this with recurrence relations.

**Bruno J.** · February 9th 2010, 02:48 PM

Originally Posted by Plato

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

Quite right! I made a mistake. I have corrected it. Thank you Plato!

**Black** · February 9th 2010, 09:02 PM

Spoiler:

**Bruno J.** · February 10th 2010, 07:18 AM

Good job, Black! You are an impressive new member.

Are you a university student?

I will post another nice solution later today.

**Bruno J.** · February 10th 2010, 08:16 AM

Here is another proof.

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

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

of the sequence $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

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

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

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

$|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 ${n \choose j} = {n \choose n-j}$ . Now just apply the binomial involution just proved!

Thread: Number of derangements of n objects

LinkBack

Thread Tools

Display

Number of derangements of n objects

Question

Similar Math Help Forum Discussions

Number of different pairings of 2n objects.

Mathematical Thinking: 2 Derangements/proof questions

Mathematical thinking proof question about derangements

Derangements(help me asap)

Number of ways in which 7 distinct objects can be put..?

Search Tags