Random permutation statistics
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 formula_1 for the set of permutations and formula_2 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 formula_6, i.e. exp, we may constrain the number of cycles" that a permutation contains, e.g. by restricting the EGF to formula_7 we obtain permutations containing two cycles. Secondly, note that the EGF of labelled cycles, i.e. of formula_8, is formula_9 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 formula_10 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 formula_12 to be the sum of its values on the cycles, then we may mark cycles of length "k" with "u" 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 formula_15 in this power series is the expected value of "b" on permutations in formula_16, given that each permutation is chosen with the same probability formula_17. This article uses the coefficient extraction operator ["z"], documented on the page for formal power series. Number of permutations that are involutions. An involution is a permutation σ so that σ = 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 formula_19 of involutions among the permutations σ ∈ "S": 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 "m"th roots of unity. This generalizes the concept of an involution. An "m"th root of unity is a permutation σ so that σ = 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 formula_23 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 formula_26 be the number of permutations on "n" whose order is exactly "d" and formula_27 the number of permutations on "n" the permutation count whose order divides "k". Then we have It follows by Möbius inversion 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 derangements), 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 formula_39 sums the coefficients of formula_40, so formula_41, the total number of derangements, is given by: Hence there are about formula_43 derangements and the probability that a random permutation is a derangement is formula_44 This result may also be proved by inclusion–exclusion. Using the sets formula_45 where formula_46 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, i.e. the number formula_51 of permutations of formula_52 containing "m" fixed points. The corresponding EGF is obtained by marking cycles of size one with the variable "u", i.e. choosing "b"("k") equal to one for formula_53 and zero otherwise, which yields the generating function formula_54 of the set of permutations  by the number of fixed points: It follows that and hence This immediately implies that for "n" large, "m" fixed. Order of a random permutation. If "P" is a permutation, the "order" of "P" is the smallest positive integer "n" for which formula_59 is the identity permutation. This is the least common multiple of the lengths of the cycles of "P". A theorem of Goh and Schmutz states that if formula_60 is the expected order of a random permutation of size "n", then where the constant "c" is Derangements containing an even and an odd number of cycles. We can  use the same construction as in the previous section to compute the number of derangements formula_63 containing an even number of cycles and the number formula_64 containing an odd number of cycles. To do this we need to mark all cycles and subtract fixed points, giving Now some very basic reasoning shows that the EGF formula_66 of formula_63 is given by We thus have which is Subtracting formula_63 from formula_41, we find The difference of these two (formula_63 and formula_64) is formula_76 One hundred prisoners. A prison warden wants to make room in his prison and is considering liberating one  hundred prisoners, thereby freeing one hundred cells. He therefore assembles one hundred prisoners and asks them to play the following game: he lines up one hundred urns in a row, each containing the name of one prisoner, where every prisoner's name occurs exactly once. The game is played as follows: every prisoner is allowed to look inside fifty urns. If he or she does not find his or her name in one of the fifty urns, all prisoners will immediately be executed, otherwise the game continues. The prisoners have a few moments to decide on a strategy, knowing that  once the game has begun, they will not be able to communicate with each other, mark the urns in any way or move the urns or the names inside them. Choosing urns at random, their chances of survival are almost zero, but there is a strategy giving them a 30% chance of survival, assuming that the names are assigned to urns randomly – what is it? First of all, the survival probability using random choices is so this is definitely not a practical strategy. The 30% survival strategy is to consider the contents of the urns to be a permutation of  the prisoners, and traverse cycles. To keep the notation simple, assign a number to each prisoner, for example by sorting their names alphabetically. The urns may thereafter be considered to contain numbers rather than names. Now clearly the contents of the urns define a permutation. The first prisoner opens the first urn. If he finds his name, he has finished and survives. Otherwise he opens the urn with the number he found in the first urn. The process repeats: the prisoner opens an urn and survives if he finds his name, otherwise he opens the urn with the number just  retrieved, up to a limit of fifty urns. The second prisoner starts with urn number two, the third with urn number three, and so on. This strategy is precisely equivalent to a traversal of the cycles of the permutation represented by the urns. Every prisoner starts with the urn bearing his number and keeps on traversing his cycle up to a limit of fifty urns. The number of the urn that contains his number is the pre-image of that number under the permutation. Hence the prisoners survive if all cycles of the permutation contain at most fifty elements. We  have to show that this probability is at least 30%. Note that this assumes that the warden chooses the permutation randomly; if the warden anticipates this strategy, he can simply choose a permutation with a cycle of length 51. To overcome this, the prisoners may agree in advance on a random permutation of their names. We consider the general case of formula_78 prisoners and formula_79 urns being opened. We first calculate the complementary probability, i.e. that there is a cycle of more than formula_79 elements. With this in mind, we introduce or so that the desired probability is because the  cycle of more than formula_79 elements will necessarily be unique. Using the fact that formula_85, we find that which yields Finally, using an integral estimate such as Euler–Maclaurin summation, or the asymptotic expansion of the "n"th harmonic number, we obtain so that or at least 30%, as claimed. A related result is that asymptotically, the expected length of the longest cycle is "λn," where λ is the Golomb–Dickman constant, approximately 0.62. This example is due to Anna Gál and Peter Bro Miltersen; consult the paper by Peter Winkler for more information, and see the discussion on "Les-Mathematiques.net". Consult  the references on 100 prisoners for links to these references. The above computation may be performed in a more simple and direct way, as follows: first note that a permutation of formula_78 elements contains at most one cycle of length strictly greater than formula_79 . Thus, if we denote then For formula_94, the number of permutations that contain a cycle of length exactly formula_95 is Expected number of transpositions of a random permutation. We can use the disjoint cycle decomposition of a permutation to factorize it as a product of transpositions by replacing a cycle of length "k" by "k" −  1 transpositions. E.g. the cycle formula_97 factors as formula_98. The function formula_99 for cycles is equal to formula_100 and we obtain and Hence the expected number of transpositions formula_103 is where formula_105 is the formula_106 Harmonic number. We could also have obtained this formula by noting that the number of transpositions is obtained by adding the lengths of all cycles (which gives "n") and subtracting one for every cycle (which gives formula_107 by the previous section). Note that formula_54 again generates the unsigned Stirling numbers of the first kind, but in reverse order. More precisely, we have To see this , note that the above is equivalent to and that which we saw to be the EGF of the unsigned Stirling numbers of the first kind in the section on permutations consisting of precisely "m" cycles. Expected cycle size of a random element. We select a random element "q" of a random permutation formula_12 and ask about the expected size of the cycle that contains "q". Here the function formula_99 is equal to formula_114, because a cycle of length "k" contributes "k" elements that are on cycles of length "k". Note that unlike the previous computations, we need to average out  this parameter after we extract it from the generating function (divide by "n"). We have Hence the expected length of the cycle that contains "q" is Probability that a random element lies on a cycle of size "m". This average parameter represents the probability that if we again select a random element of formula_52 of a random permutation, the element lies on a cycle of size "m". The function formula_99 is equal to formula_119 for formula_120 and zero otherwise, because only cycles of length "m" contribute, namely "m" elements that lie on a cycle of length "m". We have It  follows that the probability that a random element lies on a cycle of length "m" is Probability that a random subset of ["n"] lies on the same cycle. Select a random subset "Q" of ["n"] containing "m" elements and a random permutation, and ask about the probability that all elements of "Q" lie on the same cycle. This is another average parameter. The function "b"("k") is equal to formula_123, because a cycle of length "k" contributes formula_123 subsets of size "m", where formula_125 for . This yields Averaging out we obtain that the probability of the elements of "Q" being on  the same cycle is or In particular, the probability that two elements are on the same cycle is 1/2. Number of permutations containing an even number of even cycles. We may use the Flajolet–Sedgewick fundamental theorem directly and compute more advanced permutation statistics. (Check that page for an explanation of how the operators we will use are computed.) For example, the set of permutations containing an even number of even cycles is given by Translating to exponential generating functions (EGFs), we obtain or This simplifies to or This says that there is one permutation of size zero containing an  even number of even cycles (the empty permutation, which contains zero cycles of even length), one such permutation of size one (the fixed point, which also contains zero cycles of even length), and that for formula_134, there are formula_135 such permutations. Permutations that are squares. Consider what happens when we square a permutation. Fixed points are mapped to fixed points. Odd cycles are mapped to odd cycles in a one-to-one correspondence, e.g. formula_136 turns into formula_137. Even cycles split in two and produce a pair of cycles of half the size of the original cycle, e.g. formula_138 turns  into formula_139. Hence permutations that are squares may contain any number of odd cycles, and an even number of cycles of size two, an even number of cycles of size four etc., and are given by which yields the EGF Odd cycle invariants. The types of permutations presented in the preceding two sections, i.e. permutations containing an even number of even cycles and permutations that are squares, are examples of so-called odd cycle invariants, studied by Sung and Zhang (see external links). The term odd cycle invariant simply means that membership in the respective combinatorial class is independent of  the size and number of odd cycles occurring in the permutation. In fact we can prove that all odd cycle invariants obey a simple recurrence, which we will derive. First, here are some more examples of odd cycle invariants. Permutations where the sum of the lengths of the even cycles is six. This class has the specification and the generating function The first few values are Permutations where all even cycles have the same length. This class has the specification and the generating function There is a semantic nuance here. We could consider permutations containing no even cycles as belonging  to this class, since zero is even. The first few values are Permutations where the maximum length of an even cycle is four. This class has the specification and the generating function The first few values are The recurrence. Observe carefully how the specifications of the even cycle component are constructed. It is best to think of them in terms of parse trees. These trees have three levels. The nodes at the lowest level represent sums of products of even-length cycles of the singleton formula_151. The nodes at the middle level represent restrictions of the set operator. Finally the  node at the top level sums products of contributions from the middle level. Note that restrictions of the set operator, when applied to a generating function that is even, will preserve this feature, i.e. produce another even generating function. But all the inputs to the set operators are even since they arise from even-length cycles. The result is that all generating functions involved have the form where formula_153 is an even function. This means that is even, too, and hence Letting formula_156 and extracting coefficients, we find that which yields the recurrence A problem from the 2005 Putnam competition . A link to the Putnam competition website appears in the section External links. The problem asks for a proof that where the sum is over all formula_160 permutations of formula_52, formula_162 is the sign of formula_163, i.e. formula_164 if formula_163 is even and formula_166 if formula_163 is odd, and formula_168 is the number of fixed points of formula_163. Now the sign of formula_163 is given by where the product is over all cycles "c" of formula_163, as explained e.g. on the page on even and odd permutations. Hence we consider the combinatorial class where formula_174 marks one minus the length  of a contributing cycle, and formula_175 marks fixed points. Translating to generating functions, we obtain or Now we have and hence the desired quantity is given by Doing the computation, we obtain or Extracting coefficients, we find that the coefficient of formula_182 is zero. The constant is one, which does not agree with the formula (should be zero). For formula_79 positive, however, we obtain or which is the desired result. As an interesting aside, we observe that formula_186 may be used to evaluate the following determinant of an formula_187 matrix: where formula_189. Recall the formula for the determinant: Now the  value of the product on the right for a permutation formula_163 is formula_192, where "f" is the number of fixed points of formula_163. Hence which yields and finally The difference between the number of cycles in even and odd permutations. Here we seek to show that this difference is given by Recall that the sign formula_162 of a permutation formula_163 is given by where the product ranges over the cycles "c" from the disjoint cycle composition of formula_163. It follows that the combinatorial species formula_23 that reflects the signs and the cycle count of the set of permutations is given  by where we have used formula_174 to mark signs and formula_175 for the cycle count. Translating to generating functions we have This simplifies to which is Now the two generating functions formula_209 and formula_210 of even and odd permutations by cycle count are given by and We require the quantity which is Finally, extracting coefficients from this generating function, we obtain which is which is in turn This concludes the proof.