Random Permutation Statistics - Expected Number of Cycles of A Given Size m

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

\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} \frac{z^m}{m}

or

\frac{1}{m} z^m \; + \; \frac{1}{m} z^{m+1} \; + \; \frac{1}{m} z^{m+2} \; + \; \cdots

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

\frac{1}{1-z} \sum_{k=1}^m \frac{z^k}{k} \mbox{ and } \frac{1}{1-z} \sum_{k=1}^m \frac{z^k}{k} = H_m \mbox{ for } n \ge m

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:

    “Most governments have been based, practically, on the denial of equal rights of men ... ours began, by affirming those rights. They said, some men are too ignorant, and vicious, to share in government. Possibly so, said we; and, by your system, you would always keep them ignorant, and vicious. We proposed to give all a chance; and we expected the weak to grow stronger, the ignorant wiser; and all better, and happier together.”
    —Abraham Lincoln (1809–1865)

    “The growing good of the world is partly dependent on unhistoric acts; and that things are not so ill with you and me as they might have been, is half owing to the number who lived faithfully a hidden life, and rest in unvisited tombs.”
    —George Eliot [Mary Ann (or Marian)

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

    “Beauty depends on size as well as symmetry. No very small animal can be beautiful, for looking at it takes so small a portion of time that the impression of it will be confused. Nor can any very large one, for a whole view of it cannot be had at once, and so there will be no unity and completeness.”
    —Aristotle (384 B.C.–322 B.C.)