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.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$.