Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I tried to solve this problem without any success. I really hope that you will know the answer.
$f(n,m)$ presents the number of binary strings (empty string included) that include at most n times '1', and at most m times '0'.

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

share|cite|improve this question
We have $f(1,0) = 1$, but your formula gives $2$. Are you sure it's right? Edit: This was in answer to the original version of the question, before it was edited. – user155747 Jun 7 '14 at 8:52
Shouldn't it have have something to do with powers of two? – tpb261 Jun 7 '14 at 8:53

Here's the answer. Consider the number $g(n,k)$ of binary strings with exactly $k$ zeros (and at most $n$ ones). These strings can have $0,1,\ldots,n$ ones, i.e., they may look as follows

$$\underbrace{0\cdots 0}_{k \text{ times}},\qquad \underbrace{0\cdots 0}_{k \text{ times}}1,\qquad \underbrace{0\cdots 0}_{k \text{ times}}11,\:\ldots,\:\underbrace{0\cdots 0}_{k \text{ times}}\underbrace{11\ldots 1}_{n \text{ times}}$$

Of course, each time, we may distribute the $k$ zeros among a total of $k+j$ digits, for $j=0,\ldots,n$. Thus, this number is given as


It is well-known that (**)


and thus,


Now, your strings may have between $0$ and $m$ zeros. Thus, the solution to your problem is

$$f(n,m)=\sum_{k=0}^m g(n,k)=\sum_{k=0}^m\binom{k+n+1}{n}=\binom{n+1}{n}+\cdots+\binom{n+m+1}{n}$$

and applying (**) again yields


EDIT To prove (**), you can telescope. Note that $\binom{k+j}{k}=\binom{k+j+1}{k+1}-\binom{k+j}{k+1}$, so


share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.