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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was perusing the subject of Eulerian polynomials. I'm assuming the definition that the Eulerian polynomial is defined by $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of descents.

The Eulerian polynomials satisfy a standard recurrence $C_n(t)=t(1-t)C'_{n-1}(t)+ntC_{n-1}(t)$. Apparently they also satisfy the more aesthetically pleasing relation $$ C_n(t)=tC'_{n-1}(t)+t^nC'_{n-1}(t^{-1}). $$

The generating function in $t^{-1}$ is troublesome to me. How can one derive this other recurrence relation? Thank you,

share|cite|improve this question
up vote 2 down vote accepted

Write $C_{n-1}(t) = \sum_{k=1}^{n-1} a_k t^k$, and look eactly how each term contributes in $C_n(t)$ :

Your first recurrence relation says : $C_n(t) = t(1-t)C'_{n-1}(t)+ntC_{n-1}t = (t-t^2)(\sum_{k=1}^{n-1} k a_k t^{k-1}) + nt(\sum_{k=1}^{n-1} a_k t^k) \\ = \sum_{k=1}^{n-1} (k-kt+nt)a_k t^k = \sum_{k=1}^{n-1} (k + (n-k)t)a_k t^k $

Essentially, each term $t^k$ is turned into $k t^k + (n-k) t^{k+1}$ The second recurrence relation attempts to show this symmetric-looking separation :

$tC'_{n-1}(t) = \sum_{k=1}^{n-1} k a_k t^k$ : we recover the first half, which leaves us with the other half.

Since it is the same thing but in the other direction, we have to switch the coefficients of the polynomial around, differentiate, adjust the power of $t$, then switch them around again. In fact, since the Euler polynomials are symmetric, $a_k = a_{n-k}$, we can skip the first step. The last switching around step explains why you see that $C'_{n-1}(t^{-1})$ :

$\sum_{k=1}^{n-1} (n-k) a_k t^{k+1} = \sum_{k=1}^{n-1} (n-k) a_{n-k} t^{k+1} = \sum_{k=1}^{n-1} k a_k t^{n-k+1} \\ = t^n \sum_{k=1}^{n-1} k a_k (t^{-1})^{k-1} = t^n C'_{n-1}(t^{-1})$.

Even if you use $t^{-1}$, $t^n C'_{n-1}(t^{-1})$ is still a polynomial in $t$. It is a simple trick done to reverse the coefficients of a polynomial. For example, stating that the polynomials are symmetric ($a_k = a_{n-k}$), is the same as stating that $C_n(t) = t^{n+1} C_n(t^{-1})$

share|cite|improve this answer
Thanks for the explanation, mercio. – Clara Feb 13 '12 at 0:39

Your Answer


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.