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.

Possible Duplicate:
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)

Given an integer $N$, we have to count the number of possible binary strings(string is madeup of only $0$'s and $1$'s) of length $N$, and matches the regular expression pattern $[111]$. For example if $N$ is $4$, then $1110$ , $0111$ , $1111$ are the possibilities.

I have worked on it, and have got the following recurrence:

$\text{count}(a,N) = 4\text{count}(0,N-3) + 2\text{count}(1,N-3)+ \text{count}(2,N-3)$ ; if$(a == 0)$

$\text{count}(a,N) = 2\text{count}(0,N-2)+ \text{count}(1,N-1)$ ; if$(a == 1)$

$\text{count}(a,N) = \text{count}(0,N-1)$ ; if$(a == 2)$

Answer is $[(2^N) - \text{count}(0,N)]$. By using memorization, we can compute the the $\text{count}(0,N)$ in $O(N)$
but is there any better algorithm other than $O(N)$

share|improve this question

marked as duplicate by Marc van Leeuwen, William, tomasz, rschwieb, t.b. Sep 15 '12 at 22:10

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
Probably not: see this answer and the OEIS references cited there. –  Brian M. Scott Sep 7 '12 at 20:51
    
@BrianM.Scott: do you agree that is a duplicate? –  Ross Millikan Sep 7 '12 at 21:17
    
@Ross: I’m undecided: it actually does ask a slightly different (and more specific) question, but I doubt that we can come up with a better answer than we had before. –  Brian M. Scott Sep 7 '12 at 21:20
    
"memorization"? –  Gerry Myerson Sep 7 '12 at 23:12
    
@Gerry: Are you asking what it means, or do you just want it to be spelled without the "r"? –  Henning Makholm Sep 8 '12 at 1:32
show 3 more comments

1 Answer 1

Let $f(N)$ be the number of binary strings of length $N$ that do not contain "111" as a substring. (So you are interested in $2^N - f(N)$.) Every such binary string ends in exactly one of the strings "0", "01", or "011". This gives rise to the recurrence $$ f(N) = f(N-1) + f(N-2) + f(N-3), $$ the "tribonacci recurrence". The inital values are $f(1)=1$, $f(2)=2$, and $f(3)=4$. Therefore a closed form can be given that is similar to the one for the tribonacci numbers, but with different constants in front of the exponential terms.

In fact, now that I look at the tribonacci numbers, I see that this exact problem has already been linked to them (see the comment by Emeric Deutsch, Apr 27 2006).

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.