Friday, September 27, 2019

combinatorics - Combinatorial identity: summation of stars and bars

I noticed that the following identity for a summation of stars and bars held for specific k but I was wondering if someone could provide a general proof via combinatorics or algebraic manipulation. I wouldn't be surprised if this is a known result; it looks very similar to the Hockey Stick identity.



\sum_{i=0}^k {d+i-1 \choose d-1} = {d+k \choose k}




The left can be immediately rewritten as \sum_{i=0}^k {d+i-1 \choose i} if it helps inspire intuition.

No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...