Take the 2-minute tour ×
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.

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'.

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

share|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 at 8:52
1  
Shouldn't it have have something to do with powers of two? –  tpb261 Jun 7 at 8:53

1 Answer 1

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

$$g(n,k)=\sum_{j=0}^n\binom{k+j}{k}$$

It is well-known that (**)

$$\binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{k+n}{k}=\binom{k+n+1}{k+1},$$

and thus,

$$g(n,k)=\sum_{j=0}^n\binom{k+j}{k}=\binom{k+n+1}{k+1}=\binom{k+n+1}{n}.$$

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

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

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

$$\sum_{j=0}^n\binom{k+j}{k}=\sum_{j=0}^n(\binom{k+j+1}{k+1}-\binom{k+j}{k+1})=\binom{k+n+1}{k+1}-\binom{k}{k+1}=\binom{k+n+1}{k+1}.$$

share|improve this answer

Your Answer

 
discard

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.