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
    Not sure what you mean by "the reason". Do you want to know how to get the recurrence relation from another definition of these polynomials? Or the reason that somebody would want to look at those polynomials?2012-02-06
  • 0
    @RobertIsrael Sorry for being unclear, I'm curious how to get this recurrence relation.2012-02-06
  • 0
    @anon My apologies, I see what the confusion is now. I was assuming the definition of the Eulerian polynomials that I read while browsing Stanley, but didn't explicitly say so. I've now added it.2012-02-06
  • 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.