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:

“Can a woman become a genius of the first class? Nobody can know unless women in general shall have equal opportunity with men in education, in vocational choice, and in social welcome of their best intellectual work for a number of generations.”
—Anna Garlin Spencer (1851–1931)

“While I do not suggest that humanity will ever be able to dispense with its martyrs, I cannot avoid the suspicion that with a little more thought and a little less belief their number may be substantially reduced.”
—J.B.S. (John Burdon Sanderson)

“Motherhood in all its guises and permutations is more art than science.”
—Melinda M. Marshall (20th century)