2
$\begingroup$

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

$\endgroup$
3
  • $\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$ Aug 27, 2012 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$ Aug 28, 2012 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$ Aug 28, 2012 at 15:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.