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:

    “Parenting is not logical. If it were, we would never have to read a book, never need a family therapist, and never feel the urge to call a close friend late at night for support after a particularly trying bedtime scene. . . . We have moments of logic, but life is run by a much larger force. Life is filled with disagreement, opposition, illusion, irrational thinking, miracle, meaning, surprise, and wonder.”
    —Jeanne Elium (20th century)

    “Parenting is not logical. If it were, we would never have to read a book, never need a family therapist, and never feel the urge to call a close friend late at night for support after a particularly trying bedtime scene. . . . We have moments of logic, but life is run by a much larger force. Life is filled with disagreement, opposition, illusion, irrational thinking, miracle, meaning, surprise, and wonder.”
    —Jeanne Elium (20th century)

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

    “Only that which points the human spirit beyond its own limitations into what is universally human gives the individual strength superior to his own. Only in suprahuman demands which can hardly be fulfilled do human beings and peoples feel their true and sacred measure.”
    —Stefan Zweig (18811942)