# Prove Eulerian Number using Combinatorics.

For any $n ≥ 1$ and $1 ≤ k ≤ n$, define the “Eulerian number” $e(n, k)$ to be the number of permutations of $\{1, 2, . . . , n\}$ with exactly $k −1$ descents. So $e(n, 1) = e(n, n) = 1$, and $e(n, k) = 0$ if $k < 1$ or $k > n$. Prove that $e(n, k) = k · e(n − 1, k) + (n − k + 1)e(n − 1, k − 1)$, for all $n ≥ 1$ and $1 ≤ k ≤ n$. Use the recurrence to find $e(n, k)$ for all $k$, with $n ≤ 5$.

I am thinking of breaking it down into a permutation of $[n − 1]$ with either $k − 1$ or $k − 2$ descents, but I'm not sure how to prove the number of ways to insert $n$.

• Think of a permutation as the numbers $1,\ldots,n$ in some sequence. One then get a permutation of $[n]$ by inserting $n$ into a permutation of $[n-1]$... – Lord Shark the Unknown Nov 16 '17 at 6:06
• thanks. I just can't wrap my head around why there is (n-k+1) ways of inserting n such that n becomes a descent too. – wtnmath Nov 16 '17 at 18:29
• To increase the number of descents by one, either put $n$ at the start, or into an ascent. – Lord Shark the Unknown Nov 16 '17 at 18:32