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:

    “I like to compare the holiday season with the way a child listens to a favorite story. The pleasure is in the familiar way the story begins, the anticipation of familiar turns it takes, the familiar moments of suspense, and the familiar climax and ending.”
    —Fred Rogers (20th century)

    “As the tragic writer rids us of what is petty and ignoble in our nature, so also the humorist rids us of what is cautious, calculating, and priggish—about half of our social conscience, indeed. Both of them permit us, in blessed moments of revelation, to soar above the common level of our lives.”
    —Robertson Davies (b. 1913)

    “I was not at all shocked with this execution at the time. John died seemingly without much pain. He was effectually hanged, the rope having fixed upon his neck very firmly, and he was allowed to hang near three quarters of an hour; so that any attempt to recover him would have been in vain. I comforted myself in thinking that by giving up the scheme I had avoided much anxiety and uneasiness.”
    —James Boswell (1740–1795)

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