Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Robert Israel Feb 6 '12 at 1:48
    
@RobertIsrael Sorry for being unclear, I'm curious how to get this recurrence relation. –  Clara Feb 6 '12 at 5:51
    
@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. –  Clara Feb 6 '12 at 7:02
    
Awesome, good. $\text{}$ –  anon Feb 6 '12 at 7:03
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you anon. –  Clara Feb 7 '12 at 2:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.