Number of binary strings with $n$ ones and $m$ zeros

Question

$f(n,m)$ is the number of binary strings with up to $n$ ones and up to $m$ zeros.

Prove that the number of possible strings is: $${n+m+2 \choose n+1} -1$$

I got to the point that: $$\sum_{a=0}^n \sum_{b=0}^m {a+b \choose a}$$

And I also understand that there are $(n+1)$ options for the amount of ones and $(m+1)$ options for the amount of zeros.

Answer 1

As remarked by Daniel Fischer above, you can apply the "hockey stick" identities to find your sum; these are the sums going down the diagonals of Pascal's triangle:

For the inner sum, use

$\binom{a}{a}+\binom{a+1}{a}+\binom{a+2}{a}+\cdots+\binom{a+m}{a}=\binom{a+m+1}{a+1}$;

and for the outer sum, use

$\binom{m+1}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\cdots+\binom{m+n+1}{n+1}=\binom{m+n+2}{n+1}$.

(The first sum goes down a right-to-left diagonal, and the second sum goes down a left-to-right diagonal.)

Answer 2

Let $S$ be the set of binary strings of length $n+m+2$ with $n+1$ ones and $m+1$ zeroes. By definition, $$|S|=\binom{n+m+2}{n+1}.$$

Let $L \in S$. Let $\beta$ be the bit in the last place of $L$ and $\overline{\beta}$ be the complement of $\beta$.

Since $n \geq 0$ and $m \geq 0$, we know $L$ has the form $$L=(\text{substring } X,\overbrace{\overline{\beta},\overline{\beta},\ldots,\overline{\beta}}^i,\overbrace{\beta,\beta,\ldots,\beta}^j)$$ where $i \geq 1$ (and $i$ is the maximum such positive integer possible) and $j \geq 1$. We observe:

• The substring $X$ obtained is a binary string with at most $n$ ones and at most $m$ zeroes.

• Every non-empty binary string $X$ with at most $n$ ones and at most $m$ zeroes can be obtained uniquely in this way (by appending ones and zeroes to it in the appropriate way).

• The empty binary string $X$ can be obtained in exactly two ways.

Hence there are $|S|-1$ binary strings with at most $n$ ones and at most $m$ zeroes.