Random Permutation Statistics - The Fundamental Relation

The Fundamental Relation

Permutations are sets of labelled cycles. Using the labelled case of the Flajolet–Sedgewick fundamental theorem and writing for the set of permutations and for the singleton set, we have

Translating into exponential generating functions (EGFs), we have

where we have used the fact that the EGF of the set of permutations (there are n! permutations of n elements) is

This one equation will allow us to derive a surprising number of permutation statistics. Firstly, by dropping terms from, i.e. exp, we may constrain the number of cycles that a permutation contains, e.g. by restricting the EGF to we obtain permutations containing two cycles. Secondly, note that the EGF of labelled cycles, i.e. of, is

because there are k! / k labelled cycles.

This means that by dropping terms from this generating function, we may constrain the size of the cycles that occur in a permutation and obtain an EGF of the permutations containing only cycles of a given size.

Now instead of dropping, let's put different weights on different size cycles. If is a weight function that depends only on the size k of the cycle and for brevity we write

the value of b for a permutation to be the sum of its values on the cycles, then we may mark cycles of length k with ub(k) and obtain a bivariate generating function g(z, u) that describes the parameter, i.e.

g(z, u) = 1 + \sum_{n\ge 1} \left( \sum_{\sigma\in S_n} u^{b(\sigma)} \right) \frac{z^n}{n!} = \exp \sum_{k\ge 1} u^{b(k)} \frac{z^k}{k}

This is a mixed generating function which is exponential in the permutation size and ordinary in the secondary parameter u. Differentiating and evaluating at u = 1, 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} = \sum_{n\ge 1} \left( \sum_{\sigma\in S_n} b(\sigma) \right) \frac{z^n}{n!}

i.e. the EGF of the sum of b over all permutations, or alternatively, the OGF, or more precisely, PGF (probability generating function) of the expectation of b.

This article uses the coefficient extraction operator, documented on the page for formal power series.

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words fundamental and/or relation:

    “Disney World has acquired by now something of the air of a national shrine. American parents who don’t take their children there sense obscurely that they have failed in some fundamental way, like Muslims who never made it to Mecca.”
    —Simon Hoggart (b. 1946)

    “There is undoubtedly something religious about it: everyone believes that they are special, that they are chosen, that they have a special relation with fate. Here is the test: you turn over card after card to see in which way that is true. If you can defy the odds, you may be saved. And when you are cleaned out, the last penny gone, you are enlightened at last, free perhaps, exhilarated like an ascetic by the falling away of the material world.”
    —Andrei Codrescu (b. 1947)