Random Permutation Statistics - Moments of Fixed Points

Moments of Fixed Points

The mixed GF of the set of permutations by the number of fixed points is

g(z, u) = \exp\left( -z + uz + \log \frac{1}{1-z}\right) = \frac{1}{1-z} \exp ( -z + uz ).

Let the random variable X be the number of fixed points of a random permutation. Using Stirling numbers of the second kind, we have the following formula for the mth moment of X:

E(X^m) = E\left( \sum_{k=0}^m \left\{ \begin{matrix} m \\ k \end{matrix} \right\} (X)_k \right) = \sum_{k=0}^m \left\{ \begin{matrix} m \\ k \end{matrix} \right\} E((X)_k),

where is a falling factorial. Using, we have

E((X)_k) = \left(\frac{d}{du}\right)^k g(z, u) \Bigg|_{u=1} = \frac{z^k}{1-z} \exp ( -z + uz ) \Bigg|_{u=1} = \frac{z^k}{1-z},

which is zero when, and one otherwise. Hence only terms with contribute to the sum. This yields

E(X^m) = \sum_{k=0}^n \left\{ \begin{matrix} m \\ k \end{matrix} \right\}.

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words moments of, moments, fixed and/or points:

    “It is time to provide a smashing answer for those cynical men who say that a democracy cannot be honest, cannot be efficient.... We have in the darkest moments of our national trials retained our faith in our own ability to master our own destiny.”
    —Franklin D. Roosevelt (1882–1945)

    “Athletes have studied how to leap and how to survive the leap some of the time and return to the ground. They don’t always do it well. But they are our philosophers of actual moments and the body and soul in them, and of our manoeuvres in our emergencies and longings.”
    —Harold Brodkey (b. 1930)

    “Our live experiences, fixed in aphorisms, stiffen into cold epigrams. Our heart’s blood, as we write it, turns to mere dull ink.”
    —F.H. (Francis Herbert)

    “The two great points of difference between a democracy and a republic are: first, the delegation of the government, in the latter, to a small number of citizens elected by the rest; secondly, the greater number of citizens and greater sphere of country over which the latter may be extended.”
    —James Madison (1751–1836)