Number of Permutations Containing Cycles
Applying the Flajolet–Sedgewick fundamental theorem, i.e. the labelled enumeration theorem with, to the set
we obtain the generating function
The term
yields the Stirling numbers of the first kind, i.e. is the EGF of the unsigned Stirling numbers of the first kind.
We can compute the OGF of these numbers for n fixed, i.e.
Start with
which yields
Summing this, we obtain
Using the formula for on the left, the definition of on the right, and the binomial theorem, we obtain
Comparing the coefficients of, and using the definition of the binomial coefficient, we finally have
a falling factorial.
Read more about this topic: Random Permutation Statistics
Famous quotes containing the words number of, number, permutations and/or cycles:
“Strange goings on! Jones did it slowly, deliberately, in the bathroom, with a knife, at midnight. What he did was butter a piece of toast. We are too familiar with the language of action to notice at first an anomaly: the it of Jones did it slowly, deliberately,... seems to refer to some entity, presumably an action, that is then characterized in a number of ways.”
—Donald Davidson (b. 1917)
“I think, for the rest of my life, I shall refrain from looking up things. It is the most ravenous time-snatcher I know. You pull one book from the shelf, which carries a hint or a reference that sends you posthaste to another book, and that to successive others. It is incredible, the number of books you hopefully open and disappointedly close, only to take down another with the same result.”
—Carolyn Wells (18621942)
“Motherhood in all its guises and permutations is more art than science.”
—Melinda M. Marshall (20th century)
“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)