Enumerative Combinatorics: Activities and Exercises

1. A Surjection \(f: A \rightarrow A\).

Suppose that \(A\) is a finite set and that we have a surjection \(g: A \rightarrow A\text{.}\) Prove that \(g\) must be a bijection. (The key is that \(g\) maps \(A\) to itself!). Solution.

2. Left-to-Right Maxima.

Let \(q=q_1q_2 \cdots q_n\) be an \(n\)-permutation written in one-line notation. We say that \(k\) is a left-to-right maximum if \(q_k > q_i\) for \(1 \leq i < k\text{.}\) Circle all of the left-to-right maxima in the following permutation. How many are there?

Solution.

3. The Transition Lemma.

Here is the Transition Lemma:

Let \(f: S_n \rightarrow S_n\) be the mapping that takes a permutation \(p\) in canoncical cycle notation and removes all of the parentheses to create a permutation \(f(p)\) in one-line notation. Then the mapping \(f\) is a bijection.

Prove the Transition Lemma. By problem 1, you only need to show that \(f\) is surjective. Given a permutation \(q\) written in one-line notation, you must find a permutation \(p\) written in canonical cycle notation such that \(f(p)=q\text{.}\) How can you use problem 2 to help in this effort? Solution.

4. Applications of the Transition Lemma.

The Transition Lemma is particularly amazing because it can turn an interesting but hard counting problem into a easy or straight-forward counting problem. Here are two examples

1. How many \(n\)-permutations are there with \(k\) left-to-right maxima? Solution.

   By the transition lemma, each left-to-right maximum in one-line notation corresponds to the beginning of a new cycle in canonical cycle notation. Therefore the number of \(n\)-permutations with \(k\) left-to-right maxima is the same as the number of permutations with \(k\) cycles. This number is \(c(n,k)\text{,}\) the unsigned Stirling numbers of the first kind.

2. Pick an \(n\)-permutation at random from \(S_n\text{.}\) What is the probability that the cycle containing element \(n\) has length \(k\text{?}\) What is the probability that the cycle containing element \(i\) has length \(k\text{?}\) Solution.

   Using the transition mapping, we get a permutation in one-line notation with element \(n\) in position \(n-k+1\text{.}\) The total number of permutations with \(n\) in that position is \((n-1)!\text{.}\) So the probability that a random permutation has element \(n\) in position \(n-k+1\) is

   \begin{equation*} \frac{(n-1)!}{n!} = \frac{1}{n}. \end{equation*}

   By the transition lemma, this is also equal to the probability that element \(n\) is in a \(k\)-cycle.

5. Average Number of Fixed Points of a Permutation.

A fixed point of a permutation \(f\) is an element \(i\) such that \(f(i)=i\text{.}\) Use problem 4(b) to prove that the average number of fixed points of a permutation is 1 by finishing the following proof by strong induction.

• Base Case: When \(n=1\text{,}\) there is exactly one permutation: \((1)\text{.}\) This permutation has one fixed point.

• Inductive Hypothesis: Assume that if \(1<k<n\text{,}\) then the average number of fixed points in a \(k\)-permutation is \(1\text{.}\)

• Consider \(n\text{:}\) We consider the set \(S_n\) of all \(n\)-permutations. Partition \(S_n\) into sets \(A_1, A_2, \ldots, A_n\) where \(A_i\) consists of all permutations where element \(n\) is in an \(i\)-cycle.

  Now you must count the average number of fixed points in each of the \(A_i\) for the following cases:

  • Case \(i=1\text{.}\) Solution.

    In this case, \(n\) is a fixed point. The remaining elements form an \((n-1)\)-permutation. By induction, the average number of fixed points in the remaining elements is 1. Overall, there are 2 fixed points on average in the set \(A_1\text{.}\)

  • Case \(2 \leq i \leq n-1\text{.}\) Solution.

    In this case, there are no fixed points among the \(i\) elements in the cycle containing element \(n\text{.}\) By induction, there is one fixed point on average in the remaining \((n-i)\) elements.

  • Case \(i=n\text{.}\) Solution.

    In this case, all the elements are in one big cycle of length \(n\text{.}\) Therefore, there are no fixed points.

  Now use your results above to find the average number of fixed points. Solution.

  By the previous question, we have \(|A_i|=(n-1)!\) for \(1 \leq i \leq n\text{.}\) Therefore, the average number of fixed points among all \(n\)-permutations is

  \begin{equation*} \begin{array}{rcl} && \frac{2 \cdot |A_1| + 1 \cdot |A_2| + 1 \cdot |A_3| + \cdots 1 \cdot |A_{n-1}| + 0 \cdot |A_n| }{n!} \\ &=& \frac{n \cdot (n-1)!}{n!} = 1. \end{array} \end{equation*}