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.

This is an unsolved question in my textbook (so full answers are ok too). We are asked to count the number of binary numbers of length 15, beginning with '1', that have a total of ten 1s, five 0s, and two consecutive zeros.

My thoughts are, we can begin by ordering the 10 1s: $1 1 1 1 1 1 1 1 1 1$. The answer is the number of ways to put the 0s between them, which is like the number of integer solutions to $x_1+x_2+...+x_{10}=5$ with at least one $x_i>=2$. However, I don't know how to count that...

Thanks for your help.

share|improve this question
    
Your idea will work nicely for no two consecutive $0$s. Find that, subtract from total. For no two consecutive $0$, we need to choose five "gaps" to put the $0$s in. (I am assuming two means at least two.) –  André Nicolas Oct 27 '11 at 21:01
    
Listing: I get $10*C(12,3)=2200$ (10 ways to place the double-zeros and 3 ways to place the remaining 0s, but this doesn't quite make sense since without the double-zero restriction the total number of binary numbers would be $C(14,9)=2002$ (number of ways to place the 1s)... can you clarify what you mean? –  roel Oct 27 '11 at 21:07
    
Nevermind, I think I was mistaken :-], maybe there is something i overlooked I am not good at this things. –  Listing Oct 27 '11 at 21:09
1  
Andre: I'll give it a shot. We have $00000$ zeros to put in 1s between. We want at least 1 between every 0, so it's the number of positive integer solutions for $x_1+...+x_4=10$. This I know how to count: it's $C(10-1,4-1)=84$. So the answer would be $C(14,9)-84=1918$? It kind of feels too big to me... –  roel Oct 27 '11 at 21:13
    
why break the head, the soluction is only a simple fibonacci :) –  user45340 Oct 20 '12 at 2:01

3 Answers 3

up vote 3 down vote accepted

The problem is somewhat ambiguous. There are several interpretations: (a) at least two consecutive $0$'s; (b) exactly one occurrence of two consecutive $0$'s; (c) at least one occurrence of two consecutive $0$'s, and nowhere $3$ consecutive $0$'s; (d) maybe others.

We solve (a). We first count the ways to have no two consecutive $0$'s. Put the ten $1$'s in a row as in the post. There are $10$ "gaps" immediately to the right of a $1$, including the gap at the right end. We must choose $5$ of these gaps for the $0$'s. This can be done in $\binom{10}{5}$ ways.

Next we count the total number of binary numbers with $5$ $0$'s, $10$ $1$'s, that start with a $1$. From the $14$ positions left to be filled, we must choose $5$ for the $0$'s. This can be done in $\binom{14}{5}$ ways. So the number of binary strings with at least two consecutive $0$'s is $$\binom{14}{5}-\binom{10}{5}.$$

With the interpretation (b), things are simpler. We have the $10$ gaps as before. We must choose one of these gaps to have the $00$. This can be done in $\binom{10}{1}$ ways. For each way, there are $9$ gaps left for the remaining three "single" $0$'s. They can be filled in $\binom{9}{3}$ ways, for a total of $\binom{10}{1}\binom{9}{3}$.

Comments: $1.$ The number of strings with at least two consecutive $0$'s turns out to be $1750$, and the total number of strings is $2002$, so if a string is randomly chosen, the probability it will have at least two consecutive $0$'s is roughly $0.874$. This is may be substantially higher than one would guess. In this kind of situation, it is easy for intuition to fail. We kind of see the 0's as being all separated, but most of the time there will be at least some clumping. There is a similar phenomenon with a baseball batter. If he gets two hits in a row, the announcer says he's got a hot bat. But "streaks," even in a purely random setting, are more frequent than intuition suggests.

$2.$ We can attack interpretation (a) in other ways. One approach is to list the types of ways we could have one or more consecutive $0$'s, count, and add. We could have $5$ consecutive $0$'s; r we could have $4$ and a singleton; or we could have a $3$ and a $2$; or $3$ and two singletons; or two $2$'s and a singleton; or one $2$ and three singletons; or all singletons. The number of strings of each type is easily counted. But this is kind of tedious, and would get out of control if the numbers were much larger.

share|improve this answer
    
Thanks. This makes sense, but can you explain what went wrong in my solution? (In the comments to the original question) We counted the total number of ways the same way ($C(14,5)=C(14,9)$), so it looks like my next step was the wrong one. –  roel Oct 27 '11 at 21:22
    
Wait! I got it. You don't need to place all 1s between the 0s, just 4... –  roel Oct 27 '11 at 21:25
    
I take it you now see the $\binom{10}{5}$ in terms of solutions of an equation. It can be done that way, but it is not automatic, since accounting for $0$ after the initial $1$, or at the end, is slightly tricky in terms of equations. –  André Nicolas Oct 27 '11 at 21:49
    
Yeah, I found out how to correct my initial answer and got to the same (10,5) ... thanks again. :) –  roel Oct 27 '11 at 21:54

All of these numbers can be computed in GAP. We begin with:

  • 2002: The number of binary numbers with 10 ones and 5 zeroes. Computed by the following:

    T:=Filtered(PermutationsList([1,1,1,1,1,1,1,1,1,1,0,0,0,0,0]),L->L[1]=1);;
    Size(T);
    
  • 1750: The number of binary numbers with 10 ones and 5 zeroes with two consecutive zeroes somewhere. Computed by the following:

     S:=Filtered(T,L->ForAny([1..14],i->L[i]=0 and L[i+1]=0));;
     Size(S);
    
  • 1200: The number of binary numbers with 10 ones and 5 zeroes with two consecutive zeroes somewhere, and no three consecutive zeroes. Computed by the following:

     R:=Filtered(S,L->not ForAny([1..13],i->L[i]=0 and L[i+1]=0 and L[i+2]=0));;
     Size(R);
    
  • 840: The number of binary numbers 10 with ones and 5 zeroes with exactly one occurence of two consecutive zeroes. Computed by the following:

     Q:=Filtered(T,L->Size(Filtered([1..14],i->L[i]=0 and L[i+1]=0))=1);;
     Size(Q);
    

We can repeat this computation for the number of (0,1)-sequences.

  • 3003: The number of (0,1)-sequences with 10 ones and 5 zeroes. Computed by the following:

     T2:=PermutationsList([1,1,1,1,1,1,1,1,1,1,0,0,0,0,0]);;
     Size(T2);
    
  • 2541: The number of (0,1)-sequences with 10 ones and 5 zeroes with two consecutive zeroes somewhere. Computed by the following:

     S2:=Filtered(T2,L->ForAny([1..14],i->L[i]=0 and L[i+1]=0));;
     Size(S2);
    
  • 1815: The number of (0,1)-sequences with 10 ones and 5 zeroes with two consecutive zeroes somewhere, and no three consecutive zeroes. Computed by the following:

     R2:=Filtered(S2,L->not ForAny([1..13],i->L[i]=0 and L[i+1]=0 and L[i+2]=0));;
     Size(R2);
    
  • 1320: The number of (0,1)-sequences with 10 ones and 5 zeroes with exactly one occurence of two consecutive zeroes. Computed by the following:

     Q2:=Filtered(T2,L->Size(Filtered([1..14],i->L[i]=0 and L[i+1]=0))=1);;
     Size(Q2);
    

While it's a good idea to understand the material, the computer can provide a handy check of one's argument (and a means of coming up with the argument in the first place; and a means of pinpointing a flaw, if one's argument is invalid). Moreover, the code can usually be quickly modified for other slightly different applications.

share|improve this answer
    
To one not versed in GAP, this looks like more work than André Nicolas' hand solution. It is nice to have a check. –  Ross Millikan Oct 20 '12 at 3:03
    
That's why I often give computational answers -- to encourage people to become familiar with GAP's features (or other computer algebra systems; but I prefer GAP since it's free and open source). –  Douglas S. Stones Oct 20 '12 at 3:15

Nr of binary numbers with 2 consecutive zeroes is Fibbonaci (n) (where n is the nr of bits).

If you just take it step by step, from numbers with 1 digits to more, and check how many possibilities there are, you can calculate it based on previous ones, and you will notice that the recurrence is actually Fibbonacci's sequence.

Here's a nice link with an explanation http://stackoverflow.com/questions/11948007/number-of-possible-binary-strings-of-length-k

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.