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 the fundamental, fundamental and/or relation:

    “The great, the fundamental need of any nation, any race, is for heroism, devotion, sacrifice; and there cannot be heroism, devotion, or sacrifice in a primarily skeptical spirit.”
    —Anna Julia Cooper (1859–1964)

    “The science, the art, the jurisprudence, the chief political and social theories, of the modern world have grown out of Greece and Rome—not by favor of, but in the teeth of, the fundamental teachings of early Christianity, to which science, art, and any serious occupation with the things of this world were alike despicable.”
    —Thomas Henry Huxley (1825–95)

    “We must get back into relation, vivid and nourishing relation to the cosmos and the universe. The way is through daily ritual, and is an affair of the individual and the household, a ritual of dawn and noon and sunset, the ritual of the kindling fire and pouring water, the ritual of the first breath, and the last.”
    —D.H. (David Herbert)