Eulerian numbers are coefficients of Eulerian polynomial

Statement

Let $A_{n}$ be the Eulerian polynomial and $A (n, k)$ be the Eulerian numbers. Then,

A_{n} (x) = \sum_{k = 0}^{n - 1} A (n, k) x^{k}

Proof

Denote $\tilde{A} (n, k)$ the coefficient of $x^{k}$ in $A_{n} (x)$ . Then, we want to show that $\tilde{A} (n, k) = A (n, k)$ .

Recall the recurrence relation for $A_{n}$ :

A_{n + 1} (x) = (1 + n x) A_{n} (x) + x (1 - x) A_{n}^{'} (x)

Looking at the $k$ th coefficient,

\begin{aligned} \tilde{A} (n + 1, k) & = \tilde{A} (n, k) + n \tilde{A} (n, k - 1) + k \tilde{A} (n, k) - (k - 1) \tilde{A} (n, k - 1) \\ = (n - k + 1) \tilde{A} (n, k - 1) + (k + 1) \tilde{A} (n, k) \end{aligned}

(note also that this explains the recurrence in the Eulerian triangle).

Now let us show that $A (n, k)$ satisfies the same recurrence relation as $\tilde{A} (n, k)$ . We note that we can create a permutation of $S_{n + 1}$ by adding the number $n + 1$ somewhere inside of a permutation of $S_{n}$ . Where we do this affects the descent number as follows:

If we add it at an ascent, then you will have an ascent followed by a descent. The total number of descents increases by 1.
- In order for this to contribute to $A (n + 1, k)$ , it must come from $A (n, k - 1)$ and there are $n - (k - 1) = n - k + 1$ ascent spots that we can insert $n + 1$ into.
If you add it at a descent, then you will have an ascent followed by a descent. The total number of descents stays the same.
- In order for this to contribute to $A (n + 1, k)$ , it must come from $A (n, k)$ and there are $k + 1$ spots (we can insert it at the end too).

Thus, we obtain the recurrence relation

A (n + 1, k) = (n - k + 1) A (n, k - 1) + (k + 1) A (n, k)

And by induction, we can conclude that the two sequences are equal.