The statistics of random permutations, such as the
cycle structure of a
random permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...
are of fundamental importance in the
analysis of algorithms
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...
, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using
quickselect
In computer science, quickselect is a selection algorithm to find the ''k''th smallest element in an unordered list. It is also known as the kth order statistics . It is related to the quicksort sorting algorithm. Like quicksort, it was devel ...
(a cousin of
quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
) 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 permutation
A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...
s 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
In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and ...
and writing
for the set of permutations and
for the singleton set, we have
:
Translating into
exponential generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
s (EGFs), we have
:
where we have used the fact that the EGF of the
combinatorial species
In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs invol ...
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 ''u''
''b''(''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 mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series ...
in the secondary parameter ''u.'' Differentiating and evaluating at ''u'' = 1, we have
:
This is the
probability generating function In probability theory, the probability generating function of a discrete random variable is a power series representation (the generating function) of the probability mass function of the random variable. Probability generating functions are often ...
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
''n''">'z''''n'' documented on the page for
formal power series
In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...
.
Number of permutations that are involutions
An
involution
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
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
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
''g''(''z'') of these permutations is
:
This gives the explicit formula for the total number
of involutions among the permutations σ ∈ ''S''
''n'':
[
:
Dividing by ''n''! yields the probability that a random permutation is an involution.
These numbers are known as ]telephone number
A telephone number is a sequence of digits assigned to a landline telephone subscriber station connected to a telephone line or to a wireless electronic telephony device, such as a radio telephone or a mobile telephone, or to other devices f ...
s.
Number of permutations that are ''m''th roots of unity
This generalizes the concept of an involution. An ''m''th 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
Moebius, Möbius or Mobius may refer to:
People
* August Ferdinand Möbius (1790–1868), German mathematician and astronomer
* Theodor Möbius (1821–1890), German philologist
* Karl Möbius (1825–1908), German zoologist and ecologist
* Paul ...
. 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
:
It follows by Möbius inversion
Moebius, Möbius or Mobius may refer to:
People
* August Ferdinand Möbius (1790–1868), German mathematician and astronomer
* Theodor Möbius (1821–1890), German philologist
* Karl Möbius (1825–1908), German zoologist and ecologist
* Paul ...
that
:
Therefore, we have the EGF
:
The desired count is then given by
:
This formula produces e.g. for ''k'' = 6 the EGF
:
with the sequence of values starting at ''n'' = 5
:
For ''k'' = 8 we get the EGF
:
with the sequence of values starting at ''n'' = 8
:
Finally for ''k'' = 12 we get the EGF
:
with the sequence of values starting at ''n'' = 7
:
Number of permutations that are derangements
Suppose there are ''n'' people at a party, each of whom brought an umbrella. At the end of the party everyone picks an umbrella out of the stack of umbrellas and leaves. What is the probability that no one left with his/her own umbrella? This problem is equivalent to counting permutations with no fixed points (called derangement
In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points.
The number of derangements of ...
s), and hence the EGF, where we subtract out fixed points (cycles of length 1) by removing the term ''z'' from the fundamental relation is
:
Multiplication by sums the coefficients of , so , the total number of derangements, is given by:
:
Hence there are about derangements and the probability that a random permutation is a derangement is
This result may also be proved by inclusion–exclusion. Using the sets where to denote the set of permutations that fix ''p'', we have
:
This formula counts the number of permutations that have at least one fixed point.
The cardinalities are as follows:
:
Hence the number of permutations with no fixed point is
:
or
:
and we have the claim.
There is a generalization of these numbers, which is known as rencontres numbers In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set with specified numbers of fixed points: in other words, partial derangements. (''Rencontre'' is French for ''encounte ...
, i.e.
the number of permutations of