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:

    “No man will ever bring out of that office the reputation which carries him into it. The honeymoon would be as short in that case as in any other, and its moments of ecstasy would be ransomed by years of torment and hatred.”
    —Thomas Jefferson (1743–1826)

    “There are moments of existence when time and space are more profound, and the awareness of existence is immensely heightened.”
    —Charles Baudelaire (1821–1867)

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

    “He is the best sailor who can steer within the fewest points of the wind, and extract a motive power out of the greatest obstacles. Most begin to veer and tack as soon as the wind changes from aft, and as within the tropics it does not blow from all points of the compass, there are some harbors which they can never reach.”
    —Henry David Thoreau (1817–1862)