Skip to main content

Chapter 21 Average Number of Cycles in a Permutation

Let \(A(n)\) be the average number of cycles in an \(n\)-permutation. The goal of this activity is to prove that

\begin{equation*} A(n) = \sum_{i=1}^n \frac{1}{i}. \end{equation*}

Here, \(\displaystyle{H(n) = \sum_{i=1}^n \frac{1}{i}}\) is the \(n\)th Harmonic number, which is another very important sequence in mathematics.

Let \(c(n)\) denote the total number of cycles in all \(n\)-permutations. we

Exercises Practice Problems

1. Cycles in a permutation.

  1. Prove that \(\displaystyle{c(n) = \sum_{k=1}^n k \cdot c(n,k)}\text{.}\)

  2. Prove that \(\displaystyle{A(n) = \frac{c(n)}{n!}}\text{.}\)

2. The Harmonic Numbers.

  1. Use a graph to explain why \(H(n)\) is a pretty good approximation for \(\int_1^n \frac{1}{x} dx\text{.}\) What function does this integral represent?

  2. Interpret the meaning of \(A(n) = \sum_{i=1}^n \frac{1}{i}\) using your approximate function.

3. A recurrence for \(c(n)\).

We will prove the recurrence

\begin{equation*} c(n) = n \cdot c(n-1) + (n-1)! \end{equation*}

As usual, we will treat element \(n\) as special. Given an \(n\)-permutation \(f \in S_n\text{,}\) what happens when we remove element \(n\text{?}\) There are two cases

  1. Suppose that \(n\) was in a cycle by itself. Prove that the total number of cycles in such permutations is \(c(n-1) + (n-1)!\text{.}\)

  2. Suppose that \(n\) was not in a cycle by itself. Prove that the total number of cycles in such permutations is \((n-1) \cdot c(n-1)\text{.}\)

Putting together the answers from questions 2 and 3, we find that

\begin{equation*} c(n) = \Big( c(n-1) + (n-1)! \Big)+ (n-1) \cdot c(n-1) = n \cdot c(n-1) + (n-1)! \end{equation*}

as claimed at the start of the problem.

4. The main result.

Starting with the formula in problem 1(b) and the recurrence in problem 2, prove that

\begin{equation*} A(n) = \sum_{i=1}^n \frac{1}{i}. \end{equation*}