7.   Permutations


This chapter surveys combinatorial properties of permutations (orderings of the numbers 1 through N) and shows how they relate in a natural way to fundamental and widely-used sorting algorithms.


7.1 Basic Properties of Permutations


7.2 Algorithms on Permutations


7.3 Representations of Permutations


7.4 Enumeration Problems


7.5 Analyzing Properties of Permutations with CGFs


7.6 Inversions and Insertion Sort


7.7 Left-to-Right Minima and Selection Sort


7.8 Cycles and in Situ Permutation


7.9 Extremal Parameters

Selected Exercises

7.3

How many permutations of $2n$ elements have exactly two cycles, each of length $n$? How many have $n$ cycles, each of length $2$?


7.4

Which permutations of $n$ elements have the maximum number of different representations with cycles?


7.8

Write a program that will compute the canonical cycle representation corresponding to a given permutation.


7.9

Write a program that will compute the permutation corresponding to a given canonical cycle representation.


7.10

Give an efficient algorithm for computing the inversion table corresponding to a given permutation, and another algorithm for computing the permutation corresponding to a given inversion table.


7.24

Show that the number of involutions of size $N$ satisfies the recurrence $$b_{N+1} = b_N + Nb_{N-1}\quad{\rm for}\ N>0{\rm \ with\ } b_0=b_1=1.$$


7.26

Find the EGF for the number of permutations that consist only of cycles of even length. Generalize to find the EGF for the number of permutations that consist only of cycles of length divisible by $t$.


7.27

By differentiating the relation $(1-z)D(z)=e^z$ and setting coefficients equal, obtain a recurrence satisfied by the number of derangements of $N$ elements.


7.29

An arrangement of $N$ elements is a sequence formed from a subset of the elements. Prove that the EGF for arrangements is $e^z/(1-z)$. Express the coefficients as a simple sum and interpret that sum combinatorially.


7.45

Find the CGF for the total number of inversions in all involutions of length $N$. Use this to find the average number of inversions in an involution.


7.61

Use asymptotics from generating functions (see Section 5.5) or a direct argument to show that the probability for a random permutation to have $j$ cycles of length $k$ is asymptotic to the Poisson distribution $e^{-\lambda}\lambda^j/j!$ with $\lambda=1/k$.


Review Questions

Q7.1

What is the probability that a random permutation of size $n$ has exactly 2 cycles?


Q7.2

Identify the most likely and least likely events for a random permutation of size 1000. (a) no cycles of length a power of 2 (b) no cycles of length less than 5 (c) no cycles of length 1, 2, 3, or 7 (d) no cycles of length greater than 400


Q7.3

Give a ~-approximation for the proportion of permutations of $N$ elements that have an even number of singleton cycles.


Q7.4

Give a ~-approximation for the proportion of permutations of $N$ elements that have an odd number of singleton cycles.