MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

The Eulerian polynomials satisfy the recurrence relation $$x A_n(x) = \sum_{k=0}^{n} \binom{n}{k}(x-1)^{n-k} A_k(x).$$

This reminds me very much of $$0 = \sum_{k=0}^{b} \binom{b}{k}(-1)^{b-k}T_k$$ where $T_k$ counts the number of SSYT of shape $k^c$ with entries $1,2,\dots,n$ and $b=\binom{n}{c}.$

Are there any other combinatorial objects that satisfy a recurrence of length $n,$ where the summand is a binomial $\binom{n}{k}$ and with an alternating sign, in some sense? (The Eulerian polynomials yields and alternating sum for $x=0$, but the result is very unexiting.)

It feels like such recurrences arises quite naturally, and the "sign" part should make a counting argument with inclusion/exclusion easier. (The SSYT recuurence is such an example).

share|cite|improve this question
I'm a bit confused by the fact that $T_k$ does not seem to depend on $c$ or on $n$. Are you saying that for any fixed choice of $c$ and $n$, then this alternating sum is 0? – Patricia Hersh Aug 27 '12 at 21:47
T_k do depend on c and n! It counts the number of SSYT with a shape depending on c, and entries depending on n. So, fix n and c, and you'll get this recurrence. – Per Alexandersson Aug 28 '12 at 6:45
I don't have time to think about this now, but I wonder if your Eulerian polynomial relation has anything to do with the general relationship between $f$-vectors and $h$-vectors of simplicial complexes, using that the coefficients of the Eulerian polynomial are the $h$-vector of the type A Coxeter complex. I suppose this above would say something about the family of all type A Coxeter complexes? – Patricia Hersh Aug 28 '12 at 15:00

Your Answer


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

Browse other questions tagged or ask your own question.