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 moments of the past do not remain still; they retain in our memory the motion which drew them towards the future, towards a future which has itself become the past, and draw us on in their train.”
    —Marcel Proust (1871–1922)

    “Popular culture entered my life as Shirley Temple, who was exactly my age and wrote a letter in the newspapers telling how her mother fixed spinach for her, with lots of butter.... I was impressed by Shirley Temple as a little girl my age who had power: she could write a piece for the newspapers and have it printed in her own handwriting.”
    —Adrienne Rich (b. 1929)

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