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:

    “What is the structure of government that will best guard against the precipitate counsels and factious combinations for unjust purposes, without a sacrifice of the fundamental principle of republicanism?”
    —James Madison (1751–1836)

    “In relation to God, we are like a thief who has burgled the house of a kindly householder and been allowed to keep some of the gold. From the point of view of the lawful owner this gold is a gift; From the point of view of the burglar it is a theft. He must go and give it back. It is the same with our existence. We have stolen a little of God’s being to make it ours. God has made us a gift of it. But we have stolen it. We must return it.”
    —Simone Weil (1909–1943)