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:

    “Even the most subjected person has moments of rage and resentment so intense that they respond, they act against. There is an inner uprising that leads to rebellion, however short- lived. It may be only momentary but it takes place. That space within oneself where resistance is possible remains.”
    —bell hooks (b. c. 1955)

    “The government does not concern me much, and I shall bestow the fewest possible thoughts on it. It is not many moments that I live under a government, even in this world. If a man is thought- free, fancy-free, imagination-free ... unwise rulers or reformers cannot fatally interrupt him.”
    —Henry David Thoreau (1817–1862)

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

    “In writing biography, fact and fiction shouldn’t be mixed. And if they are, the fictional points should be printed in red ink, the facts printed in black ink.”
    —Catherine Drinker Bowen (1897–1973)