3
$\begingroup$

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)$

  • 0
    This question is equivalent to the newer question http://math.stackexchange.com/questions/192693/ (now closed as duplicate of the older http://math.stackexchange.com/questions/191702) and a special case of http://math.stackexchange.com/questions/192658. I find it very suspect that essentially the same question is asked, in different guises, four times in a couple of days. Voting to close.2012-09-09

1 Answers 1

2

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).