Skip to main content

Chapter 18 Recurrences for Eulerian Numbers

Given a permutation \(p=p_1 p_2 \cdots p_n\text{.}\) For \(1 \leq i \leq n-1\text{,}\) position \(i\) is an ascent when \(p_i < p_{i+1}\text{;}\) otherwise position \(i\) is a descent because \(p_i > p_{i+1}\text{.}\)

An ascending run is a sequence of ascents. A descending run is a sequence of descents.

The Eulerian Number

\begin{equation*} \begin{array}{rcl} A(n,k) &=& \mbox{# } \, n \mbox{-permutations with } k \mbox{ ascending runs} \\ &=& \mbox{# } \, n \mbox{-permutations with } k-1 \mbox{ descents} \\ \end{array} \end{equation*}

Exercises Practice Problems

1. Eulerian Number Recurrence.

In this problem you will prove the recurrence

\begin{equation*} A(n,k) = k \, A(n-1,k) + (n-k+1) A(n-1, k-1) \end{equation*}

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*}

  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.

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

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

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

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

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

    In conclusion, how many different options do you have for inserting element \(n\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{?}\)

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

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

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

    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.

  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).\(\)

2. Symmetry of Eulerian Numbers.

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

\begin{equation*} A(n,k) = A(n, n-k+1). \end{equation*}

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.