Random Permutation Statistics - Number of Permutations Containing Cycles

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

g_m(z) = \frac{1}{|S_m|} \left( \log \frac{1}{1-z} \right)^m = \frac{1}{m!} \left( \log \frac{1}{1-z} \right)^m.

The term

(-1)^{n+m} n! \; g_m(z) = \left

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.

s_n(w) = \sum_{m=0}^n \left w^m.

Start with

g_m(z) = \sum_{n\ge m} \frac{(-1)^{n+m}}{n!} \left z^n

which yields

(-1)^m g_m(z) w^m = \sum_{n\ge m} \frac{(-1)^n}{n!} \left w^m z^n.

Summing this, we obtain

\sum_{m\ge 0} (-1)^m g_m(z) w^m = \sum_{m\ge 0} \sum_{n\ge m} \frac{(-1)^n}{n!} \left w^m z^n = \sum_{n\ge 0}\frac{(-1)^n}{n!} z^n \sum_{m=0}^n \left w^m.

Using the formula for on the left, the definition of on the right, and the binomial theorem, we obtain

(1-z)^w = \sum_{n\ge 0} {w \choose n} (-1)^n z^n = \sum_{n\ge 0}\frac{(-1)^n}{n!} s_n(w) z^n.

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:

    “In this world, which is so plainly the antechamber of another, there are no happy men. The true division of humanity is between those who live in light and those who live in darkness. Our aim must be to diminish the number of the latter and increase the number of the former. That is why we demand education and knowledge.”
    —Victor Hugo (1802–1885)

    “To finish the moment, to find the journey’s end in every step of the road, to live the greatest number of good hours, is wisdom. It is not the part of men, but of fanatics, or of mathematicians, if you will, to say, that, the shortness of life considered, it is not worth caring whether for so short a duration we were sprawling in want, or sitting high. Since our office is with moments, let us husband them.”
    —Ralph Waldo Emerson (1803–1882)

    “The new shopping malls make possible the synthesis of all consumer activities, not least of which are shopping, flirting with objects, idle wandering, and all the permutations of these.”
    —Jean Baudrillard (b. 1929)

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