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:

    “The morning cup of coffee has an exhiliration about it which the cheering influence of the afternoon or evening cup of tea cannot be expected to reproduce.”
    —Oliver Wendell Holmes, Sr. (1809–1894)

    “I who have been involved with all styles of painting can assure you that the only things that fluctuate are the waves of fashion which carry the snobs and speculators; the number of true connoisseurs remains more or less the same.”
    —Pablo Picasso (1881–1973)

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

    “You will, I am sure, agree with me that ... if page 534 only finds us in the second chapter, the length of the first one must have been really intolerable.”
    —Sir Arthur Conan Doyle (1859–1930)

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