Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.