Enumerative Combinatorics: Activities and Exercises

1. Eulerian Number Recurrence.

In this problem you will prove the recurrence

As you might suspect, we will "treat element \(n\) as special." Let \(\cA(n,k)\) denote the set of \(n\)-permutations with \(k\) ascending runs (and therefore with \(k-1\) descents). Pro Tip #1: only positions \(1 \leq j \leq n-1\) are considered as ascents/descents. Position \(n\) is handled exceptionally. Pro Tip #2: Be ready to think about having \(k\) ascending runs, or \(k-1\) descents, whichever is easiest!

1. As a warm-up, let's consider \(n=4\) and \(k=3\text{,}\) so that the recurrence becomes

   \begin{equation*} A(4,3) = 3 A(3,3) + 2 A(3,2). \end{equation*}

   We list the 11 different permutations in \(\cA(4,3)\) and all \(6=3!\) permutations in \(S_3\text{.}\) Draw a line from the 4-permutation to the 3-permutation we obtain by deleting element 4.

   \begin{equation*} \begin{array}{ccccccccccc} 1432 & 2143 & 2431 & 3142 & 3214 & 3241 & 3421 & 4132 & 4213 & 4231 & 4312 \end{array} \end{equation*}
   \begin{equation*} \begin{array}{ccccccccccc} 123 & 132 & 213 & 231 & 312 & 321 \\ \end{array} \end{equation*}

   Solution.

   Here are the mappings:

   \begin{equation*} \begin{array}{c|cccccc} 123 & \\ 132 & 1432 & 4132 \\ 213 & 2143 & 4213 \\ 231 & 2431 & 4231 \\ 312 & 3142 & 4312 \\ 321 & 3214 & 3241 & 3421 \end{array} \end{equation*}

2. In part (a), you only mapped to permutations in \(\cA(3,2)\) and \(\cA(3,3)\text{.}\) Now work backwards. Given a permutation in \(\cA(3,2)\text{,}\) where can you place element 4 to create a permutation in \(\cA(4,3)\text{?}\) Now, how about when you start with a permutation in \(\cA(3,3)\text{?}\) Write down your observations. Solution.

   • For \(p \in \cA(3,2)\text{,}\) you can put a 4 at the beginning, or after the only ascent. Either choice creates a new ascent.

   • For \(p \in \cA(3,3)\text{,}\) you can put a 4 at the end, or after a descent. This preserves the total number of descents.

3. Now we start our proof for \(A(n,k)\text{.}\) Given a permutation \(p \in \cA(n,k)\text{.}\) Let \(p' \in S_{n-1}\) be the permutation obtained by removing element \(n\text{.}\) Explain why either \(p' \in \cA(n-1, k)\) or \(p' \in \cA(n-1,k-1)\text{.}\) Solution.

   In removing element \(n\text{,}\) one of two things happens.

   • If \(n\) was at the end of an ascending run of length at least 2, the number of ascending runs does not change. This includes the case where \(n\) was in the final position

   • If \(n\) was in an ascending run by itself, then the number of ascending runs goes down by one. This includes the case where \(n\) is in the first position.

4. Fixing \(p'=p_1 p_2 \cdots p_{n-1} \in \cA(n-1,k)\text{,}\) can we obtain an element of \(\cA(n,k)\) by placing element \(n\text{...}\)

   • Before \(p_1\text{?}\) Solution.

     No, because this will create a new ascending run.

   • After \(p_{n-1}\text{?}\) Solution.

     Yes: this just continues the current ascent.

   • Directly after a descent of \(p'\text{?}\) Solution.

     Yes, that descent becomes an ascent, and now there is a descent after element \(n\text{.}\)

   • Directly after an ascent of \(p'\text{?}\) Solution.

     No, this creates a new descent after element \(n\) for a total of \(k\) descents (instead of the required \(k-1\)).

   In conclusion, how many different options do you have for inserting element \(n\text{?}\) Solution.

   There are \(1 + (k-1) = k\) possible places to put element \(n\) when starting with \(p \in \cA(n-1,k)\text{.}\)

5. Fixing \(p'=p_1 p_2 \cdots p_{n-1} \in \cA(n-1,k-1)\text{,}\) can we obtain an element of \(\cA(n,k)\) by placing element \(n\text{...}\)

   • Before \(p_1\text{?}\) Solution.

     Yes, this adds a new descent, increasing our total number of descents from \(k-2\) to \(k-1\text{.}\)

   • After \(p_{n-1}\text{?}\) Solution.

     No, this does not add a new descent.

   • Directly after a descent of \(p'\text{?}\) Solution.

     No, this removes a decent and adds a decent for a net gain of zero.

   • Directly after an ascent of \(p'\text{?}\) Solution.

     Yes, this adds a descent so that we now have \(k-1\) descents.

   In conclusion, how many different options do you have for inserting element \(n\text{?}\) Pro Tip #3: Remember that you are starting with \(p' \in \cA(n-1,k-1)\text{,}\) so there are \(n-2\) total ascents/descents. Solution.

   We can insert element \(n\) in \(1 + (n-2) - (k-2) = 1 + n - k = n-k+1\) places.

6. Put together your answers from parts (d) and (e) to prove that \(\)A(n,k) = k \, A(n-1,k) + (n-k+1) A(n-1, k-1).\(\) Solution.

   When we remove element \(n\) from \(p \in \cA(n,k)\text{,}\) we either obtain an element of \(\cA(n-1,k)\) or \(\cA(n-1,k-1).\) By part (d), we obtain each \(p' \in \cA(n-1,k)\) exactly \(k\) times. By part (e), we obtain each \(p' \in \cA(n-1,k-1)\) exactly \(n-k+1\) times. This proves the recurrence.

2. Symmetry of Eulerian Numbers.

In this problem, you will prove the symmetry that we observed in the Eulerian triangle:

Let \(p = p_1 p_2 \cdots p_n \in \cA(n,k),\) so that \(p\) has \(k-1\) descents among \(p_1, p_2, \ldots p_{n-1}\text{.}\) Consider its reverse \(\overline{p} = p_n p_{n-1} \cdots p_1\text{.}\) By tracking descents (not ascending runs), explain why

• \(\overline{p} \in \cA(n,n-k+1)\text{,}\) and

• the mapping \(p \rightarrow \overline{p}\) is a bijection from \(\cA(n,k)\) to \(\cA(n,n-k+1)\text{.}\)

Pro Tip #4: The reversal mapping \(p \rightarrow \overline{p}\) is a very useful tool for investigating the structure of permutations. Solution.