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:

    “Between us two it’s not a star at all.
    It’s a new patented electric light,
    Put up on trial by that Jerseyite
    So much is being now expected of....”
    —Robert Frost (1874–1963)

    “Not too many years ago, a child’s experience was limited by how far he or she could ride a bicycle or by the physical boundaries that parents set. Today ... the real boundaries of a child’s life are set more by the number of available cable channels and videotapes, by the simulated reality of videogames, by the number of megabytes of memory in the home computer. Now kids can go anywhere, as long as they stay inside the electronic bubble.”
    —Richard Louv (20th century)

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

    “A needless Alexandrine ends the song,
    That, like a wounded snake, drags its slow length along.”
    —Alexander Pope (1688–1744)

    “Assemble, first, all casual bits and scraps
    That may shake down into a world perhaps;
    People this world, by chance created so,
    With random persons whom you do not know—”
    —Robert Graves (1895–1985)