Possible outcomes for combination using two numbers (with restricted placement)

Question

For a pattern of zeros of length N, what are the possible outcomes given that:

(1) You may replace each zero with a 1, except there cannot be two consecutive 1s. (2) The pattern must be padded with zeros at the edges (no replacement allowed) (3) You can have no 1s all the way to the maximum number allowed given the above restrictions.

Example 1: given a pattern 000 the possibilities are 000 and 010, but not 100 or 111 or 001, etc.

Example 2: given a pattern 000000 the following are acceptable combination:

000000
010000
001000
000100
000010
010100
010010
001010

I am not a mathmatician, so please be so kind as to describe in English a formula for calculating the possible outcomes.

Thank you

Answer 1

Your problem reduces to the following : find the numbers of sequences on $N'=N-2$ zeros and ones such that there is not two touching ones (you take those sequences, and add a zero at each extremity).

For $N'=1$, there are two sequences : $0$ and $1$ (which lead to $000$ and $010$ for $N=3$).

For $N'=2$, there are three sequences : $00$, $01$ and $10$.

To count the number of sequences for $N'\ge3$, you can :

1) add a zero to any sequence of length $N'-1$,

2) add a zero then a one to any sequence of length $N'-2$.

As any sequence either ends with a zero, or a one preceded by a zero, you must be in one case or the other, but not both.

So if $u_n$ is the number of sequences of length $n$ with no two touching ones, $(u_n)$ verifies :

1) $u_1=1$, $u_2=3$ 2) $(\forall n)\,u_{n+2}=u_{n+1}+u_n$.

Mathematically, $(u_n)$ is a linear combination of two geometric sequences of rate $\rho$ and $-\frac{1}{\rho}$, where $\rho$ is the golden ratio $\frac{1+\sqrt5}{2}$ : $$u_n = \alpha\rho^n+\beta(-\frac{1}{\rho})^n$$ Adjust $\alpha$ and $\beta$ so that the formula fits the valuers of $u_1$ and $u_2$. I'm too lazy to finish the computations :-)

Answer 2

The answer is the $(N-2)$nd Fibonacci number. The mandatory 0s on the two ends can be deleted, and then we're asking how many strings of 0s and 1s of length $N-2$ there are with no two consecutive 1s. (Note that the "replacement" mechanic is a red herring; we can just count the legal strings themselves.) This is a problem that people have answered before; here is one source (there they disallow consecutive 0s rather than consecutive 1s, but the count is the same).