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:

“In many ways, life becomes simpler [for young adults]. . . . We are expected to solve only a finite number of problems within a limited range of possible solutions. . . . It’s a mental vacation compared with figuring out who we are, what we believe, what we’re going to do with our talents, how we’re going to solve the social problems of the globe . . .and what the perfect way to raise our children will be.”
—Roger Gould (20th century)

“Of all reformers Mr. Sentiment is the most powerful. It is incredible the number of evil practices he has put down: it is to be feared he will soon lack subjects, and that when he has made the working classes comfortable, and got bitter beer into proper-sized pint bottles, there will be nothing left for him to do.”
—Anthony Trollope (1815–1882)

“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)