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:

    “Accidents will occur in the best-regulated families; and in families not regulated by that pervading influence which sanctifies while it enhances ... in short, by the influence of Woman, in the lofty character of Wife, they may be expected with confidence, and must be borne with philosophy.”
    —Charles Dickens (1812–1870)

    “In this world, which is so plainly the antechamber of another, there are no happy men. The true division of humanity is between those who live in light and those who live in darkness. Our aim must be to diminish the number of the latter and increase the number of the former. That is why we demand education and knowledge.”
    —Victor Hugo (1802–1885)

    “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 I heard a ragged noise and mirth
    Of thieves and murderers: there I him espied
    Who straight, Your suit is granted,said, and died.”
    —George Herbert (1593–1633)

    “It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
    —Hannah Arendt (1906–1975)