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:

    “Most governments have been based, practically, on the denial of equal rights of men ... ours began, by affirming those rights. They said, some men are too ignorant, and vicious, to share in government. Possibly so, said we; and, by your system, you would always keep them ignorant, and vicious. We proposed to give all a chance; and we expected the weak to grow stronger, the ignorant wiser; and all better, and happier together.”
    —Abraham Lincoln (1809–1865)

    “Can a woman become a genius of the first class? Nobody can know unless women in general shall have equal opportunity with men in education, in vocational choice, and in social welcome of their best intellectual work for a number of generations.”
    —Anna Garlin Spencer (1851–1931)

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

    “At length upon the lone Chorasmian shore
    He paused, a wide and melancholy waste
    Of putrid marshes.”
    —Percy Bysshe Shelley (1792–1822)

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