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