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:

    “Twenty can’t be expected to tolerate sixty in all things, and sixty gets bored stiff with twenty’s eternal love affairs.”
    —Emily Carr (1871–1945)

    “My idea is that the world outside—the so-called modern world—can only pervert and degrade the conceptions of the primitive instinct of art and feeling, and that our only chance is to accept the limited number of survivors—the one- in-a-thousand of born artists and poets—and to intensify the energy of feeling within that radiant centre.”
    —Henry Brooks Adams (1838–1918)

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

    “Punishment followed on a grand scale. For ten days, an unconscionable length of time, my father blessed the palms of his child’s outstretched, four-year-old hands with a sharp switch. Seven strokes a day on each hand; that makes one hundred forty strokes and then some. This put an end to the child’s innocence.”
    —Christoph Meckel (20th century)

    “Novels as dull as dishwater, with the grease of random sentiments floating on top.”
    —Italo Calvino (1923–1985)