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:

    “I know that I will always be expected to have extra insight into black texts—especially texts by black women. A working-class Jewish woman from Brooklyn could become an expert on Shakespeare or Baudelaire, my students seemed to believe, if she mastered the language, the texts, and the critical literature. But they would not grant that a middle-class white man could ever be a trusted authority on Toni Morrison.”
    —Claire Oberon Garcia, African American scholar and educator. Chronicle of Higher Education, p. B2 (July 27, 1994)

    “States strong enough to do good are but few.
    Their number would seem limited to three.”
    —Robert Frost (1874–1963)

    “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 they all to merry London came,
    To merry London, my most kindly nurse,
    That to me gave this life’s first native source;
    Though from another place I take my name,
    An house of ancient fame.”
    —Edmund Spenser (1552?–1599)

    “... the random talk of people who have no chance of immortality and thus can speak their minds out has a setting, often, of lights, streets, houses, human beings, beautiful or grotesque, which will weave itself into the moment for ever.”
    —Virginia Woolf (1882–1941)