Random Permutation Statistics - Expected Number of Cycles of Any Length of A Random Permutation | Expected Number Cycles Length 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:

“There were ghosts that returned to earth to hear his phrases,
As he sat there reading, aloud, the great blue tabulae.
They were those from the wilderness of stars that had expected more.
There were those that returned to hear him read from the poem of life,
Of the pans above the stove, the pots on the table, the tulips among them.
They were those that would have wept to step barefoot into reality....”
—Wallace Stevens (1879–1955)

“... in every State there are more women who can read and write than the whole number of illiterate male voters; more white women who can read and write than all Negro voters; more American women who can read and write than all foreign voters.”
—National Woman Suffrage Association. As quoted in History of Woman Suffrage, vol. 4, ch. 13, by Susan B. Anthony and Ida Husted Harper (1902)

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

“Rivers must have been the guides which conducted the footsteps of the first travelers. They are the constant lure, when they flow by our doors, to distant enterprise and adventure; and, by a natural impulse, the dwellers on their banks will at length accompany their currents to the lowlands of the globe, or explore at their invitation the interior of continents.”
—Henry David Thoreau (1817–1862)

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