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:

    “Ancient history has an air of antiquity. It should be more modern. It is written as if the specator should be thinking of the backside of the picture on the wall, or as if the author expected that the dead would be his readers, and wished to detail to them their own experience.”
    —Henry David Thoreau (1817–1862)

    “The quality of moral behaviour varies in inverse ratio to the number of human beings involved.”
    —Aldous Huxley (1894–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)

    “Unless a group of workers know their work is under surveillance, that they are being rated as fairly as human beings, with the fallibility that goes with human judgment, can rate them, and that at least an attempt is made to measure their worth to an organization in relative terms, they are likely to sink back on length of service as the sole reason for retention and promotion.”
    —Mary Barnett Gilson (1877–?)

    “And catch the gleaming of a random light,
    That tells me that the ship I seek is passing, passing.”
    —Paul Laurence Dunbar (1872–1906)