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:

    “Einstein is not ... merely an artist in his moments of leisure and play, as a great statesman may play golf or a great soldier grow orchids. He retains the same attitude in the whole of his work. He traces science to its roots in emotion, which is exactly where art is also rooted.”
    —Havelock Ellis (1859–1939)

    “I mean, we all have moments of deja vu, but this was ridiculous.”
    —Stanley Kubrick (b. 1928)

    “It is not merely the likeness which is precious ... but the association and the sense of nearness involved in the thing ... the fact of the very shadow of the person lying there fixed forever! It is the very sanctification of portraits I think—and it is not at all monstrous in me to say ... that I would rather have such a memorial of one I dearly loved, than the noblest Artist’s work ever produced.”
    —Elizabeth Barrett Browning (1806–1861)

    “It’s my feeling that God lends you your children until they’re about eighteen years old. If you haven’t made your points with them by then, it’s too late.”
    —Betty Ford (b. 1918)