Recurrence $C_n(t)=t(1-t)C'_{n-1}(t)+ntC_{n-1}(t)$ for Eulerian Polynomials?

157 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.