1
$\begingroup$

I was reading about Eulerian polynomials on OEIS, and there is a recurrence given for them, namely: $ C_0(t)=1 $ and C_n(t)=t(1-t)C'_{n-1}(t)+ntC_{n-1}(t)\qquad (n\geq 1).

How can this recurrence relation be derived? I'm taking the definition of Euler polynomials to be $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of descents of $\pi$, as can be found on page 22 of Stanley's Enumerative combinatorics. I read of them there during my self-study, but found this recurrence indepedently on OEIS, so I assume there are equivalent.

Thanks.

  • 0
    Awesome, good. $\text{}$2012-02-06

1 Answers 1

2

The online version of Stanley's Enumerative Combinatorics Vol I. proves it on page 40. Basically,

$A_d(x)=\sum_{w\in S_n}x^{1+\operatorname{des}(w)}=\sum_{k=1}^n A(d,k)x^k, \tag{D}$

where $A(d,k)$ counts the permutations in $S_n$ with $k-1$ descents. Rewrite the recurrence to get

$A(d+1,k)=kA(d,k)+(d-k+2)A(d,k-1) \tag{R}$

We can explicitly construct permutations in $S_{d+1}$ with $k-1$ descents by either adding a "$d+1$" after a descent's beginning letter (in word notation) or at the end of a permutation in $S_d$ with $k$ descents, or dually choose a permutation of $S_d$ with $k-2$ descents and put "$d+1$" somewhere that is not right after a descent's beginning letter, including in the very front of the word. This is a bijective proof that both sides of the recurrence $\rm (R)$ are equal.