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 proportion as our inward life fails, we go more constantly and desperately to the post office. You may depend on it, that the poor fellow who walks away with the greatest number of letters, proud of his extensive correspondence, has not heard from himself this long while.”
    —Henry David Thoreau (1817–1862)

    “In a number of other cultures, fathers are not relegated to babysitter status, nor is their ability to be primary nurturers so readily dismissed.... We have evidence that in our own society men can rear and nurture their children competently and that men’s methods, although different from those of women, are imaginative and constructive.”
    —Kyle D. Pruett (20th century)

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