Recall that aderangementof a set is a permutation of having no fixed points, i.e. . If the number of derangements of is , show that

.

Hint :

Spoiler:

Printable View

- Feb 9th 2010, 02:54 PMBruno J.Number of derangements of n objects
Recall that a

*derangement*of a set is a permutation of having no fixed points, i.e. . If the number of derangements of is , show that

.

Hint :

__Spoiler__:

- Feb 9th 2010, 03:02 PMwonderboy1953Question
Is the same as ?

- Feb 9th 2010, 03:03 PMBruno J.
No! is the factorial and is the number of derangements of a set having elements.

- Feb 9th 2010, 03:15 PMDrexel28
- Feb 9th 2010, 03:19 PMBruno J.
Haha... well yeah, that would certainly complete your proof! (Giggle)

- Feb 9th 2010, 03:30 PMPlato
- Feb 9th 2010, 03:30 PMDrexel28
- Feb 9th 2010, 03:48 PMBruno J.
- Feb 9th 2010, 10:02 PMBlack
__Spoiler__: - Feb 10th 2010, 08:18 AMBruno 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, 09:16 AMBruno J.
Here is another proof.

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

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

and so . Extracting the coefficient of on both sides we obtain as required.

Now let us partition the set of permutations of as follows; let denote those permutations which have precisely fixed points, for . Clearly there are ways of picking the elements which are to be fixed, and the remaining elements have to be deranged. So . Since the are clearly distinct we have

because . Now just apply the binomial involution just proved!