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:

    “At times it seems that the media have become the mainstream culture in children’s lives. Parents have become the alternative. Americans once expected parents to raise their children in accordance with the dominant cultural messages. Today they are expected to raise their children in opposition to it.”
    —Ellen Goodman (20th century)

    “It seems to me that there must be an ecological limit to the number of paper pushers the earth can sustain, and that human civilization will collapse when the number of, say, tax lawyers exceeds the world’s total population of farmers, weavers, fisherpersons, and pediatric nurses.”
    —Barbara Ehrenreich (b. 1941)

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

    “And my spirit is grown to a lordly great compass within,
    That the length and the breadth and the sweep of the marshes of
    Glynn
    Will work me no fear like the fear they have wrought me of yore
    When length was failure, and when breadth was but bitterness sore,
    And when terror and shrinking and dreary unnamable pain
    Drew over me out of the merciless miles of the plain,—
    Oh, now, unafraid, I am fain to face
    The vast sweet visage of space.”
    —Sidney Lanier (1842–1881)

    “And catch the gleaming of a random light,
    That tells me that the ship I seek is passing, passing.”
    —Paul Laurence Dunbar (1872–1906)