number of binary sets - combinatorics

Question

Just ran into this question:

let $f(n,m)$ be the number of binary strings where there are at most $n$ 1's and at most $m$ 0's.

the empty string also counts as a string.

show that $f(n,m)=\binom{n+m+2}{n+1}-1$.

thanks in advance,

Yaron.

Answer 1

This is a pretty direct proof. One would really hope for a combinatorial proof.

The obvious expression is $f(n,m)=\sum_{i=0}^n\sum_{j=0}^m \binom{i+j}{i}$.

But $$\sum_{j=0}^m\binom{i+j}{i}=\binom{i+m+1}{i+1}=\binom{i+m+1}{m}$$

So $$f(n,m)=\sum_{i=0}^n \binom{i+m+1}{m} = -1 + \sum_{i=0}^{n+1}\binom{i+m}{m} = \binom{m+n+1+1}{m+1}-1$$

Which is the result you wanted.

This is using twice the identity $\sum_{k=0}^A \binom{B+k}{B} = \binom{B+A+1}{B+1}$, the first time with $A=m$ and $B=i$, the second time with $A=n+1$ and $B=i$.