Skip to main content

Chapter 20 Cycle Structure of Permutations

We quickly review the proof technique of strong induction. The basic framework is:

Base Case: Typically, you prove the statement is true for \(n=0\) or \(n=1\text{.}\)

Inductive Step: Assume the statement is true for all \(k < n\text{.}\)

Prove True for \(n\text{:}\) Using the truth of the inductive step (for all \(k<n\)), prove that the statement is true for \(n\text{.}\)

In (weak) induction, we relate the size \(n\) case to the size \(n-1\) case. In strong induction, we relate the size \(n\) case to the size \(k\) case for some \(k<n\text{.}\) Sometimes this is the more natural way to reduce the problem size.

Exercises Practice Problems

1. Cycle Decomposition of Permutations.

Use strong induction to prove that all \(n\)-permutations can be decomposed into a union of disjoint cycles.

2. A Permutation Identity.

Prove the following identity in two different ways: \[ \sum_{k=1}^{n-1} k \cdot k! = n! - 1 \mbox{ for } n \geq 2. \]

  1. Give a combinatorial proof of this identity.

    1. Consider a non-identity permutation \(p_1p_2 \cdots p_n\text{.}\) Let \(0 \leq j \leq n-1\) be the largest integer such that \(p_1p_2 \cdots p_j = 12 \cdots (j-1)\text{.}\) That is, the first \(j-1\) elements map to themselves, but element \(j\) does not map to \(j\text{.}\) Prove that the number of such \(n\)-permutations is \((n-j) \cdot (n-j)!\text{.}\)

    2. The RHS counts the number of permutations except for the identity permutation. Explain why the LHS counts the same set. (Hint: use part (a), of course!)

  2. Prove the identity using (weak) induction.