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 suspect this problem involves a recurrence relation, but I can't figure out how to start... Can someone help me?

thanks!

share|improve this question
    
Does 0000000 count? How about 1000111? –  J. M. Oct 1 '11 at 23:15
    
@J.M. I think both of those have more than one instance of two consecutive zeros, i.e. ..(00)0.. and ..0(00).. are distinct examples. –  anon Oct 1 '11 at 23:19
    
Well, I was kind of wondering which of 0000000,1000000, or 1111100 would be "first"... –  J. M. Oct 1 '11 at 23:23
    
0000000 does not count, as it has 7 consecutive zeros. The elements being counted are: 0011111, 0011110, 0011101, 0011010, and so on –  marcos Oct 1 '11 at 23:33

2 Answers 2

up vote 4 down vote accepted

There’s no real need to look for a recurrence when you want the answer only for a single short length. $7$ is so small that it’s probably easiest to do it by hand. The cases are $001xxxx$, $1001xxx$, $x1001xx$, and their mirror images.

  • $x1001xx$: The first bit is arbitrary, and the last two can be anything but $00$, for a total of $2\cdot 3=6$ strings.

  • $1001xxx$: How many of the $8$ possible continuations are ruled out?

  • $001xxxx$: Break this into the subcases $0011xxx$ and $0010xxx$ and use what you’ve already done.

Don’t forget to double to account for the mirror images. Does this count anything twice (i.e., is any acceptable string its own mirror image)?

If you need the general solution, Ross’s approach is as straightforward as any.

share|improve this answer

Hint: If you let A(n) be the number of n-bit strings without two consecutive zeros and ending in 1, B(n) be the number of n-bit strings with two consecutive zeros and ending in 1, C(n) be the number of n-bit strings without two consecutive zeros and ending in 0, D(n) be the number of n-bit strings with two consecutive zeros and ending in 0, you can set up a set of linked recurrences. Imagine adding each of 1 and 0 to each type of string and find where it goes. Then your final answer is B(7)+D(7). A good check is to define E(n) as the number of strings that have failed, either by having three zeros in a row or having two sets of two. Then you should have accounted for all the strings.

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.