# A nicer recurrence for the Eulerian polynomials.

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,

-

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})$

-
Thanks for the explanation, mercio. – Clara Feb 13 '12 at 0:39