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:

    “The dissenter is every human being at those moments of his life when he resigns momentarily from the herd and thinks for himself.”
    —Archibald MacLeish (1892–1982)

    “The average Kentuckian may appear a bit confused in his knowledge of history, but he is firmly certain about current politics. Kentucky cannot claim first place in political importance, but it tops the list in its keen enjoyment of politics for its own sake. It takes the average Kentuckian only a matter of moments to dispose of the weather and personal helath, but he never tires of a political discussion.”
    —For the State of Kentucky, U.S. public relief program (1935-1943)

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

    “If I were in the unenviable position of having to study my work my points of departure would be the “Naught is more real ...” and the “Ubi nihil vales ...” both already in Murphy and neither very rational.”
    —Samuel Beckett (1906–1989)