Random Permutation Statistics - Expected Number of Cycles of Any Length of A Random Permutation

Expected Number of Cycles of Any Length of A Random Permutation

We construct the bivariate generating function using, where is one for all cycles (every cycle contributes one to the total number of cycles).

Note that has the closed form

and generates the unsigned Stirling numbers of the first kind.

We have

\frac{\partial}{\partial u} g(z, u) \Bigg|_{u=1} = \frac{1}{1-z} \sum_{k\ge 1} b(k) \frac{z^k}{k} = \frac{1}{1-z} \sum_{k\ge 1} \frac{z^k}{k} = \frac{1}{1-z} \log \frac{1}{1-z}.

Hence the expected number of cycles is, or about .

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words expected, number, cycles, length and/or random:

    “What strikes me as odd now is how much my father managed to get across to me without those heart-to-hearts which I’ve read about fathers and sons having in the study or in the rowboat or in the car.... Somehow I understood completely how he expected me to behave, in small matters as well as large, even though I can’t remember being given any lectures about it beyond the occasional, undramatic “You might as well be a mensch.””
    —Calvin Trillin (20th century)

    “My tendency to nervousness in my younger days, in view of the fact of a number of near relatives on both my father’s and mother’s side of the house having become insane, gave some serious uneasiness. I made up my mind to overcome it.... In the cross-examination of witnesses before a crowded court-house ... I soon found I could control myself even in the worst of testing cases. Finally, in battle.”
    —Rutherford Birchard Hayes (1822–1893)

    “The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
    —Linda Goodman (b. 1929)

    “With the ancient is wisdom; and in length of days understanding.”
    —Bible: Hebrew Job, 12:12.

    “We should stop looking to law to provide the final answer.... Law cannot save us from ourselves.... We have to go out and try to accomplish our goals and resolve disagreements by doing what we think is right. That energy and resourcefulness, not millions of legal cubicles, is what was great about America. Let judgment and personal conviction be important again.”
    —Philip K. Howard, U.S. lawyer. The Death of Common Sense: How Law Is Suffocating America, pp. 186-87, Random House (1994)