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:

    “Who among us has not, in moments of ambition, dreamt of the miracle of a form of poetic prose, musical but without rhythm and rhyme, both supple and staccato enough to adapt itself to the lyrical movements of our souls, the undulating movements of our reveries, and the convulsive movements of our consciences? This obsessive ideal springs above all from frequent contact with enormous cities, from the junction of their innumerable connections.”
    —Charles Baudelaire (1821–1867)

    “Self-expression is not enough; experiment is not enough; the recording of special moments or cases is not enough. All of the arts have broken faith or lost connection with their origin and function. They have ceased to be concerned with the legitimate and permanent material of art.”
    —Jane Heap (c. 1880–1964)

    “I, who travel most often for my pleasure, do not direct myself so badly. If it looks ugly on the right, I take the left; if I find myself unfit to ride my horse, I stop.... Have I left something unseen behind me? I go back; it is still on my road. I trace no fixed line, either straight or crooked.”
    —Michel de Montaigne (1533–1592)

    “There are good points about all such wars. People forget self. The virtues of magnanimity, courage, patriotism, etc., etc., are called into life. People are more generous, more sympathetic, better, than when engaged in the more selfish pursuits of peace.”
    —Rutherford Birchard Hayes (1822–1893)