I know it is possible to count the number of reinterpretations of ones and zeros in binary of any given digit using the simple law $2^n$, but I want to remove the duplicate count where $11$, or $111$ is present. Only $1010$, $01$, $0101$ but not $0110$. I mean no double $1$s should neighboring each other. Is there any laws for that?

  • $\begingroup$ Is e.g. 1001 allowed (for $n=4$)? What about 0010? $\endgroup$ Oct 15, 2016 at 13:05
  • $\begingroup$ allowed.. Only 2 or more ones cannot stay together like 11 or 111 $\endgroup$
    – sadek
    Oct 15, 2016 at 13:06
  • $\begingroup$ The number of binary strings of length $n$ without consecutive 1's is $F_{n+2}$, where $F_j$ means the $j$th Fibonacci number: math.stackexchange.com/questions/1935926/… $\endgroup$
    – user940
    Oct 15, 2016 at 13:22

2 Answers 2


It follows the Fibonacci sequence, starting with $$2,3,5,8,13,21,\dots$$

To see why, visualize the branching tree of the process. Each $0$ in there gives us two possible continuations, $0$ and $1$, while $1$ only allows $0$ to follow. This is equivalent to the well-known "rabbit-scenario" formulation of the Fibonacci sequence, where a rabbit must mature (go from being a $1$ to being a $0$) before it can reproduce.


Yes it's simple to find that for given length $n$. Let $dp[i][j]$ denote the answer for length $i$ and ending at $j$.
$dp[1][1] = dp[1][0] = 1$.
For $i>1$,
$dp[i][0] = dp[i-1][0]+dp[i-1][1]$
$dp[i][1] = dp[i-1][0]$
Answer would be $dp[n][0]+dp[n][1]$

  • $\begingroup$ Why downvote? Its correct. $\endgroup$
    – maverick
    Oct 15, 2016 at 13:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .