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).

  • $\begingroup$ 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? $\endgroup$ – Patricia Hersh Aug 27 '12 at 21:47
  • $\begingroup$ 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. $\endgroup$ – Per Alexandersson Aug 28 '12 at 6:45
  • $\begingroup$ 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? $\endgroup$ – Patricia Hersh Aug 28 '12 at 15:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.