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.

Say n is 8.

How would I ever solve this problem? I've Googled around and searched this site but I haven't come up with much. I'm not even looking for the answer necessarily, just the process by which I'd go about getting it.

I started by calculating the total number of bit strings of length 8 as $2^8$. From there where should I go?

share|improve this question
    
Would you count $0000$ as containing 3 consecutive $0$s or are you limiting the count to those strings that contain 3 consecutive $0$s and no more? –  Rick Decker Jan 15 '13 at 21:56

1 Answer 1

up vote 2 down vote accepted

You can define $A(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in $1$, $B(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in one $0$, , $C(n)$ as the number of strings of length $n$ not containing three $0$'s and ending in two $0$'s, and $D(n)$ as the number of strings of length $n$ containing three zeros. Then $A(1)=1$, $B(1)=1$, $C(1)=0$, $D(1)=0$ and for $n>1$, $$ \begin{align} A(n)&=A(n-1)+B(n-1)+C(n-1) \\ B(n)&=A(n-1)\\ C(n)&=B(n-1)\\ D(n)&=2D(n-1)+C(n-1) \end{align} $$

share|improve this answer
    
@Doug Smith: This answer presumes that you want to count all strings with at least one run of at least three zeros. –  Ross Millikan Jan 15 '13 at 21:59
    
I edited your answer since in my browser some of the text overlapped the "Related" items on the right of the page. Feel free to revert if you wish. –  Rick Decker Jan 15 '13 at 22:05
1  
Unless I misread, I got $D(4)=2$ but there are three such strings of length 4: $0000$, $0001$, $1000$. –  Rick Decker Jan 15 '13 at 22:18
1  
@RickDecker: Yes, I lost the coefficient of $2$ on $D$. You can add either a zero or one to a string that already has three zeros. –  Ross Millikan Jan 15 '13 at 22:20
1  
@Rick, the founder of the Online Encyclopedia of Integer Sequences is spelled Sloane, not Sloan. Also, link. –  Henning Makholm Jan 15 '13 at 22:44

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.