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:

    “It is time to provide a smashing answer for those cynical men who say that a democracy cannot be honest, cannot be efficient.... We have in the darkest moments of our national trials retained our faith in our own ability to master our own destiny.”
    —Franklin D. Roosevelt (1882–1945)

    “Parenting is not logical. If it were, we would never have to read a book, never need a family therapist, and never feel the urge to call a close friend late at night for support after a particularly trying bedtime scene. . . . We have moments of logic, but life is run by a much larger force. Life is filled with disagreement, opposition, illusion, irrational thinking, miracle, meaning, surprise, and wonder.”
    —Jeanne Elium (20th century)

    “But see, the Virgin blest
    Hath laid her Babe to rest:
    Time is our tedious song should here have ending;
    Heaven’s youngest teemed star,
    Hath fixed her polished car,
    Her sleeping Lord with handmaid lamp attending;
    And all about the courtly stable,
    Bright-harnessed angels sit in order serviceable.”
    —John Milton (1608–1674)

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