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)

    “It is an immense loss to have all robust and sustaining expletives refined away from one! At ... moments of trial refinement is a feeble reed to lean upon.”
    —Alice James (1848–1892)

    “Indeed, I thought, slipping the silver into my purse ... what a change of temper a fixed income will bring about. No force in the world can take from me my five hundred pounds. Food, house and clothing are mine for ever. Therefore not merely do effort and labour cease, but also hatred and bitterness. I need not hate any man; he cannot hurt me. I need not flatter any man; he has nothing to give me.”
    —Virginia Woolf (1882–1941)

    “A few ideas seem to be agreed upon. Help none but those who help themselves. Educate only at schools which provide in some form for industrial education. These two points should be insisted upon. Let the normal instruction be that men must earn their own living, and that by the labor of their hands as far as may be. This is the gospel of salvation for the colored man. Let the labor not be servile, but in manly occupations like that of the carpenter, the farmer, and the blacksmith.”
    —Rutherford Birchard Hayes (1822–1893)