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