# How many ways I can permute the $n$ digits binary without counting the neighboring $1$s?

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?

• Is e.g. 1001 allowed (for $n=4$)? What about 0010? Oct 15, 2016 at 13:05
• allowed.. Only 2 or more ones cannot stay together like 11 or 111 Oct 15, 2016 at 13:06
• 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/…
– user940
Oct 15, 2016 at 13:22

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