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. Solution.
Base Case: \(n=1\) When \(n\)=1, there is only one permutation structure: \((1)\text{,}\) which is the disjoint union of one cycle.
Inductive Step: Assume that for \(k<n\text{,}\) every \(k\)-permutation can be decomposed into the union of disjoint cycles.
Prove True for \(n\text{:}\) Consider any \(n\)-permutation \(f \in S_n\text{.}\) Suppose that element \(n\) has order \(r\text{.}\) This means that \[ (n, f(n) , f^2(n), \ldots, f^{r-1}(n)) \] is a cycle in the permutation \(n\text{.}\) Considering remaining \(n-r\) elements, we know that \(f\) must permute these elements among themselves. In other words, restricting \(f\) to these \(k=n-r\) elements gives a \(k\)-permutation. By strong induction, we can represent this mapping as the union of disjoint cycles. Along with the disjoint \(r\)-cycle containing \(n\text{,}\) we now have a decomposition of the original permutation \(f\text{.}\)
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. \]
-
Give a combinatorial proof of this identity.
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{.}\) Solution.
Fix \(j\) where \(1 \leq j \leq n\text{.}\) Suppose that \(p_1p_2 \cdots p_{j-1} = 12 \cdots (j-1)\text{,}\) and \(p_{j} \neq j.\)
There is one way to assign \(p_1 p_2 \cdots p_{j-1} = 12 \cdots (j-1)\text{.}\)
There are \(n-j\) choices for \(p_{j}\) (since we have \(p_{j} \neq j\) and the first \(j-1\) elements have already been taken).
There are \((n-j)!\) ways to assign the last \(n-j\) entries to the remaining \(n-j\) elements.
By the product principle, the total number of ways to create the permutation is
\begin{equation*} 1 \cdot (n-j) \cdot (n-j)! \end{equation*}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!) Solution.
If \(p=p_1 p_2 \cdots p_n\) is not the identity permutation, then there is some index \(j\) such that \(p_j \neq j\text{.}\) Note that \(1 \leq j \leq n-1\) because the value \(j=n\) is impossible (if the first \(n-1\) elements map to themselves, then so does the last element, Partitioning the set of non-identity permutations according to the first such index \(j\text{,}\) we get
\begin{equation*} \sum_{j=1}^{n-1} (n-j) \cdot (n-j)! = \sum_{k=1}^{n-1} k \cdot k! \end{equation*}
Prove the identity using (weak) induction. Solution.
Base Case: \(n=2\) The LHS is \(1 \cdot 1! = 1\) and the RHS is \(2!-1=1\text{.}\)
Inductive Step: Assume that \(\)\sum_{k=1}^{n-2} k \cdot k! = (n-1)! - 1.\(\)
Prove True for \(n\text{:}\) \​begin{eqnarray*} \sum_{k=1}^{n-1} k \cdot k! &=& (n-1) \cdot (n-1)! + \sum_{k=1}^{n-2} k \cdot k! \\ &=& (n-1) \cdot (n-1)! + (n-1)! - 1 \mbox{ by the inductive assumption} \\ &=& n! -1. \end{eqnarray*}