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

  • 1
    Probably not: see [this answer](http://math.stackexchange.com/a/191709/12042) and the OEIS references cited there.2012-09-07
  • 0
    @BrianM.Scott: do you agree that is a duplicate?2012-09-07
  • 0
    @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.2012-09-07
  • 0
    "memorization"?2012-09-07
  • 0
    @Gerry: Are you asking what it means, or do you just want it to be spelled without the "r"?2012-09-08
  • 0
    @Henning, a bit of both, actually. It's only recently I've come across the word, "memoization", and at first I thought it was a typo for "memorization". I still don't know quite what it means (so I should just go look it up somewhere, I know), and I think it's funny that here we may have "memorization" as a typo for "memoization".2012-09-08
  • 0
    [See this](http://math.stackexchange.com/a/192287/26068) and [this](http://math.stackexchange.com/questions/191335/finding-a-n-for-very-large-n-where-a-n-a-n-1-a-n-2-a-n-3-2n) to solve the problem in $O(\lg n)$ time.2012-09-08
  • 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