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)

    “As the tragic writer rids us of what is petty and ignoble in our nature, so also the humorist rids us of what is cautious, calculating, and priggish—about half of our social conscience, indeed. Both of them permit us, in blessed moments of revelation, to soar above the common level of our lives.”
    —Robertson Davies (b. 1913)

    “Words can have no single fixed meaning. Like wayward electrons, they can spin away from their initial orbit and enter a wider magnetic field. No one owns them or has a proprietary right to dictate how they will be used.”
    —David Lehman (b. 1948)

    “A bath and a tenderloin steak. Those are the high points of a man’s life.”
    —Curtis Siodmak (1902–1988)