We wish to count the number of sequences of 0\'s and 1\'s that do not contain th

Question

We wish to count the number of sequences of 0's and 1's that do not contain three consecutive 0's. In particular, we would like to figure out how many such sequences there are of length 15. Figure out some way of solving this problem without using a computing device. (You will not find a simple formula, but you should be able to figure out some sort of pattern which will enable you to get the answer without doing too much arithmetic. In particular, the answer is too large to actually write out all possible sequences in a reasonable amount of time.) Once you have answered this question, figure out the probability that a sequence of 0's and 1's, at random (0 and 1 equally likely) of length 15 will not have three consecutive 0's.

Explanation / Answer

Answer

As the length of 15 will be too long. I'll try to keplain how you can proceed to answer this through sequence of length 6.

Lets start with all 0's

0 0 0 0 0 0

Now the main focus of the question is that there should not be 3 consecutive 0's

So the possible arrangements are:

1 1 1 1 1 1 ---------no 0's

1 1 1 1 1 0 ----------one 0...this will have further arrangements

1 1 1 1 0 1

1 1 1 0 1 1

1 1 0 1 1 1

1 0 1 1 1 1

0 1 1 1 1 1

1 1 1 1 0 0 ---------2 0's this will have further arrangements

1 1 1 0 0 1

1 1 0 0 1 1

1 0 0 1 1 1

0 0 1 1 1 1

1 1 1 0 1 0 --------0's separated from each other

1 1 0 1 1 0

1 0 1 1 1 0

0 1 1 1 1 0

0 1 1 1 0 1

0 1 1 0 1 1

0 1 0 1 1 1

So, this is how you'll have to move the 0's among the 1's keeping in mind that 3 0's cannot be together.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.