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:

\left| A_p \right| = (n-1)!\;, \; \; \left| A_p \cap A_q \right| = (n-2)!\;, \; \; \left| A_p \cap A_q \cap A_r \right| = (n-3)!\;, \; \ldots

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

or

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:

    “My tendency to nervousness in my younger days, in view of the fact of a number of near relatives on both my father’s and mother’s side of the house having become insane, gave some serious uneasiness. I made up my mind to overcome it.... In the cross-examination of witnesses before a crowded court-house ... I soon found I could control myself even in the worst of testing cases. Finally, in battle.”
    —Rutherford Birchard Hayes (1822–1893)

    “To finish the moment, to find the journey’s end in every step of the road, to live the greatest number of good hours, is wisdom. It is not the part of men, but of fanatics, or of mathematicians, if you will, to say, that, the shortness of life considered, it is not worth caring whether for so short a duration we were sprawling in want, or sitting high. Since our office is with moments, let us husband them.”
    —Ralph Waldo Emerson (1803–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)