Given a binary string , find all "legal"strings with more than consecutive 2 1's.

Question

Given a binary string {${x_{1},x_{2},x_{3},...,x_{n}}$} find all "legal" strings with more than $2$ consecutive ($ 1's)$.

For example for $N=7$ , we have $16$

With $3 (1's)$: {$1,1,1,0,0,0,0$} , {$0,1,1,1,0,0,0$} , {$0,0,1,1,1,0,0$} , {$0,0,0,1,1,1,0$} , {$0,0,0,0,1,1,1$}

With $4 (1's)$: {$1,1,1,1,0,0,0$} , {$0,1,1,1,1,0,0$} , {$0,0,1,1,1,1,0$} ,{$0,0,0,1,1,1,1$}

With $5 (1's)$: {$1,1,1,1,1,0,0$} , {$0,1,1,1,1,1,0$} ,{$0,0,1,1,1,1,1$}

With $6 (1's)$: {$1,1,1,1,1,1,0$} , {$0,1,1,1,1,1,1$} , {$1,1,1,0,1,1,1$}

With $7 (1's)$: {$1,1,1,1,1,1,1$}

Is there elegant way to calculate the number of such "legal "sub strings for any $N$.

$ Edit: $ A "legal" string is a string in which all consecutive $(1's)$ are with length $\geq 3$

Answer 1

Let $B_n$ count the number of $n$-bit strings in which any $1$'s come in Bunches of $3$ or more. This is the count we want. Let $A_n$ count the number of $n$-bit strings which can start with an Arbitrary number of $1$'s, but as soon as a $0$ appears, any subsequent $1$'s occur in bunches of $3$ or more. It's easy to see that $B_1=B_2=1$ and $B_3=2$, while $A_1=2$, $A_2=3$, and $A_3=4$. What's important is the entangled recursion for $n\ge4$:

$$\begin{align} A_n&=A_{n-1}+B_{n-1}\\ B_n&=B_{n-1}+A_{n-3} \end{align}$$

That is, if the first digit of an $A$-type string is a $1$, the remaining $n-1$ digits are of $A$-type, while if the first digit is a $0$, the rest must be of $B$-type; likewise, if the first digit of a $B$-type string is a $0$, the remaining $n-1$ digits must be of $B$-type, while if the first digit is a $1$, then the next two must also be $1$'s, but the remaining $n-3$ digits can start with an arbitrary number of $1$'s, i.e., they are of $A$-type.

We can now compute

$$\begin{align} A_4&=4+2=6\\ B_4&=2+2=4\\ \\ A_5&=6+4=10\\ B_5&=4+3=7\\ \\ A_6&=10+7=17\\ B_6&=7+4=11\\ \\ A_7&=17+11=28\\ B_7&=11+6=17 \end{align}$$

Note, $B_7=17$ agrees with what the OP found for $N=7$, provided you include the all-$0$ string $\{0,0,0,0,0,0,0\}$ in the count.

Answer 2

Consider a binary string with $s$ "$1$"'s and $m=n-s$ "$0$"'s in total. Let's put an additional (dummy) fixed $0$ at the start and at the end of the string. We individuate as a run the consecutive $1$'s between two zeros, thereby including runs of null length.

With this scheme we have a fixed number of $m+1$ runs. If we sequentially enumerate the length of each run so individuated, we construct a bijection with the number of weak compositions of $s$ into $m+1$ parts.

In your case we want that each part be either $0$ or greater than $2$, i.e. $$ \eqalign{ & N_s (s,m) = \cr & = {\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm integer}\;x_{\,j} \in \left\{ 0 \right\} \cup \left\{ {3,4, \cdots ,\left( s \right)} \right\} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,m + 1} = s \hfill \cr} \right.\quad = \cr & = \sum\limits_{0\, \le \,k\, \le \,m + 1} {\left( \matrix{ m + 1 \cr k \cr} \right){\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm integer}\;x_{\,j} \left\{ {3,4, \cdots ,\left( s \right)} \right\} \hfill \cr x_{\,1} + x_{\,2} + \; \cdots \; + x_{\,k} = s \hfill \cr} \right.} \quad = \cr & = \sum\limits_{0\, \le \,k\, \le \,m + 1} {\left( \matrix{ m + 1 \cr k \cr} \right){\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{ {\rm integer}\;y_{\,j} \left\{ {1,2, \cdots ,\left( {s - k} \right)} \right\} \hfill \cr y_{\,1} + y_{\,2} + \; \cdots \; + y_{\,k} = s - 2k \hfill \cr} \right.} \quad \cr} $$

The set in $y$ corresponds to the (standard) compositions of $s-2k$ into $k$ parts, thus $$ \eqalign{ & N_s (s,m) = \sum\limits_{0\, \le \,k\, \le \,\min \left( {m + 1,\,s/3} \right)} { \binom{m+1}{k} \binom{s-1-2k}{k-1} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,\min \left( {m + 1,\,s/3} \right)} \right)} { \binom{m+1}{m+1-k} \binom{s-1-2k}{s-3k} } \cr} $$

And the number you ask (also considering the null string) follows easily to be $$ \eqalign{ & N(n) = \sum\limits_{0\, \le \,s\, \le \,n} {\;\sum\limits_{0\, \le \,k\,\left( { \le \,\min \left( {m + 1,\,s/3} \right)} \right)} { \binom{m+1}{m+1-k} \binom{s-1-2k}{s-3k} } } = \quad \quad (1) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n/3} \right)} {\;\sum\limits_{0\, \le \,s\, \le \,n} { \binom{n+1-s}{n+1-k-s} \binom{s-1-2k}{s-3k} }} = \quad \quad (2) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n/3} \right)} {\;\left( {\left( {\sum\limits_{0\, \le \,s\, \le \,n + 1} { \binom{n+1-s}{n+1-k-s} \binom{s-1-2k}{s-3k} } } \right) - \left( \matrix{0 \cr 0 - k \cr} \right)\left( \matrix{ n - 2k \cr n + 1 - 3k \cr} \right) } \right)} = \quad \quad (3) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n/3} \right)} {\sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,n + 1} \right)} { \binom{n+1-s}{n+1-k-s} \binom{s-1-2k}{s-3k} } } = \quad \quad (4) \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,(n + 1)/4} \right)} { \binom{n+1-2k}{n+1-4k} } \quad \quad (5) \cr} $$ where:
(2) : exchange summation order and replace $m$ with $n-s$;
(3) : extend the summation in $s$ to the whole range and deducting the term $s=n+1$;
(4) : the subtracted term is null everywhere;
(5) : "double convolution".

So finally
the number of binary strings where the ones - if present - appears only in runs of three or more consecutive
is given by the closed sum $$ N(n) = \sum\limits_{0\, \le \,k\,\left( { \le \,(n + 1)/4} \right)} { \binom{n+1-2k}{n+1-4k} } $$

Note that for $n=0,\cdots, 10$ we get for $N$ $$1, 1, 1, 2, 4, 7, 11, 17, 27, 44, 72$$ which checks with the answer by Barry Cipra, with $$ B_{\,n} = N(n)\quad A_{\,n} = \sum\limits_{0\, \le \,k\,} { \binom{n+1-2k}{n-4k} } $$