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:

“There is not to be found, in all history, any miracle attested by a sufficient number of men, of such unquestioned good sense, education, and learning, as to secure us against all delusion in themselves ... beyond all suspicion of any design to deceive others ... and at the same time attesting facts, performed in such a public manner, and in so celebrated a part of the world, as to render the detection unavoidable.”
—David Hume (1711–1776)

“At thirty years a woman asks her lover to give her back the esteem she has forfeited for his sake; she lives only for him, her thoughts are full of his future, he must have a great career, she bids him make it glorious; she can obey, entreat, command, humble herself, or rise in pride; times without number she brings comfort when a young girl can only make moan.”
—Honoré De Balzac (1799–1850)

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