Expected Number of Cycles of A Given Size m
In this problem we use a bivariate generating function g(z, u) as described in the introduction. The value of b for a cycle not of size m is zero, and one for a cycle of size m. We have
or
This means that the expected number of cycles of size m in a permutation of length n less than m is zero (obviously). A random permutation of length at least m contains on average 1/m cycles of length m. In particular, a random permutation contains about one fixed point.
The OGF of the expected number of cycles of length less than or equal to m is therefore
where Hm is the mth harmonic number. Hence the expected number of cycles of length at most m in a random permutation is about ln m.
Read more about this topic: Random Permutation Statistics
Famous quotes containing the words expected, number, cycles and/or size:
“She has been mans slave. He has been educated at her expense. If he bought the ice cream, she was expected to pay for all his luxuries in reduced wages. She has done the drudgery and borne the insults of those who wronged her, assuming to be her protector.”
—Caroline Nichols Churchill (1833?)
“Coles Hill was the scene of the secret night burials of those who died during the first year of the settlement. Corn was planted over their graves so that the Indians should not know how many of their number had perished.”
—For the State of Massachusetts, U.S. public relief program (1935-1943)
“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)
“Eat your meals according to the size of your bowl.”
—Chinese proverb.


