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, fixed and/or points:

    “Who among us has not, in moments of ambition, dreamt of the miracle of a form of poetic prose, musical but without rhythm and rhyme, both supple and staccato enough to adapt itself to the lyrical movements of our souls, the undulating movements of our reveries, and the convulsive movements of our consciences? This obsessive ideal springs above all from frequent contact with enormous cities, from the junction of their innumerable connections.”
    —Charles Baudelaire (1821–1867)

    “I was not at all shocked with this execution at the time. John died seemingly without much pain. He was effectually hanged, the rope having fixed upon his neck very firmly, and he was allowed to hang near three quarters of an hour; so that any attempt to recover him would have been in vain. I comforted myself in thinking that by giving up the scheme I had avoided much anxiety and uneasiness.”
    —James Boswell (1740–1795)

    “Mankind is not a circle with a single center but an ellipse with two focal points of which facts are one and ideas the other.”
    —Victor Hugo (1802–1885)