The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions.
The article on random permutations contains an introduction to random permutations.
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 combinatorial species of permutations (there are n! permutations of n elements) is
This one equation allows one to derive a large 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.
Instead of removing and selecting cycles, one can also 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
defining 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 two-variable generating function
This is a "mixed" generating function: it is an exponential generating function in z and an ordinary generating function in the secondary parameter u. Differentiating and evaluating at u = 1, we have
This is the probability generating function of the expectation of b. In other words, the coefficient of in this power series is the expected value of b on permutations in , given that each permutation is chosen with the same probability .
This article uses the coefficient extraction operator [zn], documented on the page for formal power series.
Number of permutations that are involutions
An involution is a permutation σ so that σ2 = 1 under permutation composition. It follows that σ may only contain cycles of length one or two, i.e. the exponential generating function g(z) of these permutations is
This gives the explicit formula for the total number of involutions among the permutations σ ∈ Sn:
Dividing by n! yields the probability that a random permutation is an involution. These numbers are known as telephone numbers.
Number of permutations that are mth roots of unity
This generalizes the concept of an involution. An mth root of unity is a permutation σ so that σm = 1 under permutation composition. Now every time we apply σ we move one step in parallel along all of its cycles. A cycle of length d applied d times produces the identity permutation on d elements (d fixed points) and d is the smallest value to do so. Hence m must be a multiple of all cycle sizes d, i.e. the only possible cycles are those whose length d is a divisor of m. It follows that the EGF g(x) of these permutations is
When m = p, where p is prime, this simplifies to
Number of permutations of order exactly k
This one can be done by Möbius inversion. Working with the same concept as in the previous entry we note that the combinatorial species of permutations whose order divides k is given by
Translation to exponential generating functions we obtain the EGF of permutations whose order divides k, which is
Now we can use this generating function to count permutations of order exactly k. Let be the number of permutations on n whose order is exactly d and the number of permutations on n the permutation count whose order divides k. Then we have