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.

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

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.