1
$\begingroup$

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?

$\endgroup$

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.