The number of integer compositions of an integer $n$ with exactly $m$ zeros is counted by the formula

$\sum_{j=1}^n \binom{n-1}{j-1}\binom{m+j}{m}$,

which is easy to see combinatorically since $\binom{n-1}{j-1}$ counts the integer compositions of $n$ in $j$ positive parts and the term $\binom{m+j}{m}$ distributes the $m$ zero parts among a total of $m+j$ parts. Surely, any such composition can have between $j=1$ and $j=n$ parts with positive integers and must have exactly $m$ zero parts.

Now, why does

$\sum_{j=1}^n 2^{j-1}\binom{m+1}{n-(j-1)}\binom{n-1}{j-1}$

count the same thing? Does anyone have a simple combinatorial interpretation of the last equation (in terms of counting integer compositions with exactly $m$ zeros)? Is the identity between the two above binomial coefficient formulas known?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.