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 \(f: A \rightarrow A\text{.}\) Prove that \(f\) must be a bijection. (The key is that \(f\) maps \(A\) to itself!).

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?

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?

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?

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{?}\)

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{.}\)

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

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

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