Random Permutation Statistics - Number of Permutations That Are Derangements

Number of Permutations That Are Derangements

Suppose there are n people at a party, each of whom brought an umbrella. At the end of the party everyone picks an umbrella out of the stack of umbrellas and leaves. What is the probability that no one left with his/her own umbrella? This problem is equivalent to counting permutations with no fixed points, and hence the EGF (subtract out fixed points by removing z) g(x) is

$\exp \left( -z + \sum_{k\ge 1} \frac{z^k}{k} \right) = \frac{e^{-z}}{1-z}.$

Now multiplication by just sums coefficients, so that we have the following formula for, the total number of derangements:

Hence there are about derangements and the probability that a random permutation is a derangement is

This result may also be proved by inclusion-exclusion. Using the sets where to denote the set of permutations that fix p, we have

$\left| \bigcup_p A_p \right| = \sum_p \left| A_p \right| \; - \; \sum_{p<q} \left| A_p \cap A_q \right| \; + \; \sum_{p<q<r} \left| A_p \cap A_q \cap A_r \right| \; - \; \cdots \; \pm \; \left| A_p \cap \; \cdots \; \cap A_s \right|.$

This formula counts the number of permutations that have at least one fixed point. The cardinalities are as follows:

Hence the number of permutations with no fixed point is

$n! \; \; - \; \; {n \choose 1} (n-1)! \; \; + \; \; {n \choose 2} (n-2)! \; \; - \; \; {n \choose 3} (n-3)! \; \; + \; \; \cdots \; \; \pm \; \; {n \choose n} (n-n)!$

$n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$

and we have the claim.

There is a generalization of these numbers, which is known as rencontres numbers, i.e. the number of permutations of containing m fixed points. The corresponding EGF is obtained by marking cycles of size one with the variable u, i.e. choosing b(k) equal to one for and zero otherwise, which yields the generating function of the set of permutations by the number of fixed points:

$g(z, u) = \exp \left( -z + uz + \sum_{k\ge 1} \frac{z^k}{k} \right) = \frac{e^{-z}}{1-z} e^{uz}.$

It follows that

$g(z, u) = \frac{e^{-z}}{1-z} \frac{z^m}{m!}$

and hence

$D(n, m) = n! g(z, u) = \frac{n!}{m!} \frac{e^{-z}}{1-z} = \frac{n!}{m!} \sum_{k=0}^{n-m} \frac{(-1)^k}{k!}.$

This immediately implies that

$D(n, m) = {n \choose m} D(n-m, 0) \; \; \mbox{ and } \; \; \frac{D(n, m)}{n!} \approx \frac{e^{-1}}{m!}$

for n large, m fixed.

Read more about this topic: Random Permutation Statistics

Famous quotes containing the words number of, number and/or permutations:

“The poetic act consists of suddenly seeing that an idea splits up into a number of equal motifs and of grouping them; they rhyme.”
—Stéphane Mallarmé (1842–1898)

“As equality increases, so does the number of people struggling for predominance.”
—Mason Cooley (b. 1927)

“The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
—Jean Baudrillard (b. 1929)