The number of binary strings of length $n$ without the sequence (1;0;1) in it. [duplicate]

Question

First i know that a similat question had been answered here: The number of binary strings of length $n$ with no three consecutive ones But i am really a numb on this subject so i want to be sure to understand it correctly.

But my question is a little bit different as i am looking for the number of binary word of length $n$ without a different sequence, more precisally without the sequence $(1;0;1)$ in it.

Let writte $s_{n}$ all the correct sequence of length $n$.
So $s_{n}=s_{n-1}0 + s_{n-1, valid}1$ that means the total number of valid sequences of length $n$ equal the total number of valid sequences length $n-1$ that end with a zero + the total number of valid sequences length $n-1$ that end with a 1.
No matter what is the valid sequence of length $n-1$ if we add a zero at the end our sequence is still valid. The difficulty is concerning: $s_{n-1, valid}1$. Indeed if $s_{n-1}$ is a valid sequence of length $n-1$ that end with $10$ if we add a $1$ at the end to it we get the forbidden sequence.

So let focus on the total number of valid sequence of length $n-1$ that end with a $1$ $s_{n-1, valid}1 = s_{n-2}11 + s_{n-2, valid}01$
Now we encounter the same difficulty as describe above for $s_{n-2, valid}01$. But similarly we can writte:$s_{n-2,valid}01=s_{n-3}001$
That means that the only valid sequences of length $n-2$ that after we add 01 to them are still valid sequences of numbers are the one who finish with a zero.

So we can conclude that:
$s_{n}=s_{n-1}0+s_{n-1, valid}1=s_{n-1}0+s_{n-2}11+s_{n-2, valid}01=s_{n-1}0+s_{n-2}11+s_{n-3}001$
So: $s_{n}=s_{n-1}+s_{n-2}+s_{n-3}$
With as initial condition: $s_1=2, s_2=4$ and $s_3=7=2^3-1$

Am i correct?

Answer 1

Addendum added to respond to the comment/question of X0-user-0X.

---

A case can be made that this response is not on point, because I have not attempted to critique your specific approach.

I would opt for a simpler approach. Given that the outlawed sequence is (1,0,1), I would define the following $3$ variables:

• $s(n,1)$ denotes the number of all satisfying sequences of length $n$, whose rightmost digit is $(1).$

• $s(n,0)$ denotes the number of all satisfying sequences of length $n$, whose rightmost digit is $(0).$

• $s(n)$ denotes the number of all satisfying sequences of length $n$.

This yields the following formulas:

• $s(n) = s(n,1) + s(n,0).$

• $s(n,0) = s(n-1).$
  The idea here is that when constructing a satisfying sequence of length $(n)$, that ends in $(0)$, all satisfying sequences of length $(n-1)$ may be extended.

• $s(n,1) = s(n-1,1) + [s(n-1,0) - s(n-2,1)].$
  The idea is that when constructing a satisfying sequence of length $(n)$, that ends in $(1)$, all satisfying sequences of length $(n-1)$ that end in $(1)$ can be extended.
  
  Further, those satisfying sequences of length $(n-1)$ that end in $(0)$ can also be extended, unless the sequence of length $(n-1)$ specifically ends in $(1,0)$.
  
  Note that the number of satisfying sequences of length $(n-1)$ that end in $(1,0)$, is exactly equal to the number of satisfying sequences of length $(n-2)$ that end in $(1)$.
  
  This explains the $[s(n-1,0) - s(n-2,1)]$ expression.
  
  Therefore, $s(n,1) = s(n-1) - s(n-2,1).$

---

Putting this all together:

$$s(n) = 2s(n-1) - s(n-2,1).$$

$$s(n-2,1) = s(n-2) - s(n-2,0) = s(n-2) - s(n-3).$$

Therefore,

$$s(n) = 2s(n-1) - [s(n-2) - s(n-3)]$$

$$= 2s(n-1) - s(n-2) + s(n-3). \tag1 $$

(1) above is the exact same intermediate formula alternatively derived in Mateo's answer. Mateo's answer then used this intermediate formula to derive the formula in the comment of Daniel Mathias.

---

Addendum
Responding to the comment/question of X0-user-0X.

But can you tell me where i am wrong (in my answer)?

This is a very fair question. I had trouble analyzing your posting, because I was not sure what your variables represented. So, in order to attempt to spot your mistake, I will have to guess at what you are saying.

In analyzing your posting, I will need to express your ideas in terms of the variables/syntax used in my answer.

That is:

• $s(n,1)$ denotes the number of all satisfying sequences of length $n$, whose rightmost digit is $(1).$

• $s(n,0)$ denotes the number of all satisfying sequences of length $n$, whose rightmost digit is $(0).$

• $s(n)$ denotes the number of all satisfying sequences of length $n$.

So, I will take a guess at where I think that you made your first mistake. Since I am guessing, I may be mistaken. If so, leave an additional comment following my answer, and I will dive deeper into your analysis. It will help me analyze your work if we $\color{red}{\text{both adopt the syntax/variables that I use in my answer}}.$

Since my critique is guess-work, I will stop, once I find what appears to be your first mistake. Then, I will ask you to consider whether my response in the Addendum + my original answer resolves your question.

If not, please leave an additional comment/question, and I will dive deeper into your question.

---

Let write $s_{n}$ all the correct sequence of length $n$.
So $s_{n}=s_{n-1}0 + s_{n-1, valid}1$ that means the total number of valid sequences of length $n$ equal the total number of valid sequences length $n-1$ that end with a zero + the total number of valid sequences length $n-1$ that end with a 1.
No matter what is the valid sequence of length $n-1$ if we add a zero at the end our sequence is still valid. The difficulty is concerning: $s_{n-1, valid}1$. Indeed if $s_{n-1}$ is a valid sequence of length $n-1$ that end with $10$ if we add a $1$ at the end to it we get the forbidden sequence.

I am confused by what the following equation is asserting:

$$s_{n}=s_{n-1}0 + s_{n-1, valid}1 \tag2 $$

The first portion of the above excerpt seems to indicate that you are using the syntax $s_{n-1}0$ to represent $s(n-1,0)$.

The second portion of the above excerpt seems to indicate that you are using the syntax $s_{n-1}0$ to represent $s(n,0)$.

This needs to be nailed down. If you are using $s_{n-1}0$ to represent $s(n-1,0)$, then this is wrong, because then the equation at the start of your excerpt becomes

$$s(n) = s(n-1,0) + s(n-1,1),$$

when it should instead be

$$s(n) = s(n,0) + s(n,1).$$

If I have not resolved your question, then, before proceeding further, please overhaul/edit your posting to adopt my syntax. Then, after you leave the additional comment following my answer, it will be easier for me to dive more deeply into your posting.

Answer 2

This is my try.

Let $S_n=\{x\in\{0,1\}^n:\text{there are no }101\}$. Let $s_n=\# S_n$.

Let $J_n^k=\{x\in S_n:x\text{ ends in }0\underbrace{11\ldots l}_{k\text{ times}}\}$ for $k<n$ and $J_n^n=\{(11\ldots 1)\}$ and $j_n^k=\# J_n^k$.

Then

• $j_n^n=j_n^{n-1}=1$ (trivial)
• $j_n^k = s_{n-k-2}$ for $0<k<n-1$, where we put $s_0=1$. The reason is that if $x\in J_n^k$ then $x$ ends on $0011\ldots 1$ and the digits before this suffix is arbitrary from $s_{n-k-2}$.
• $j_n^0=s_{n-1}$ (as above).
• $S_n$ is a disjoint union of the sets $J_n^k$ for $0\leq k\leq n$.
• Therefore $s_n=s_{n-1}+s_{n-3}+\cdots+s_1+s_0+1+1$.
• So $s_{n-1}=s_{n-2}+s_{n-4}+\cdots+s_1+s_0+1+1$.
• Subtracting these two equations we obtain $s_n=2s_{n-1}-s_{n-2}+s_{n-3}$. This is the desired formula.

Inspired by Daniel Mathias' comment, I decided to calculate more: adding two formulae $$\begin{cases}s_n &=2s_{n-1}-s_{n-2}+s_{n-3}\\ s_{n-1} &=2s_{n-2}-s_{n-3}+s_{n-4}\end{cases}$$ we get $$s_n = s_{n-1} + s_{n-2}+s_{n-4}.$$

Answer 3

Hint: First I'd like to point at the somewhat problematic part of OPs conclusion. Let's have a look at \begin{align*} s_{n}&=s_{n-1}0+s_{n-1, \text{valid}}1\\ &=s_{n-1}0+\color{blue}{s_{n-2}11}+s_{n-2, \text{valid}}01\\ &=s_{n-1}0+s_{n-2}11+s_{n-3}001\\ \\ &s_{n}\stackrel{?}{=}s_{n-1}+s_{n-2}+s_{n-3} \end{align*}

The pitfall here is the blue marked part $\color{blue}{s_{n-2}11}$. We are not allowed to take any valid sequence of length $n-2$ followed by $11$, since there are valid sequences ending in $10$ which combined with $11$ give the invalid sequence $\color{blue}{101}1$.

Note: Besides the nicely given answers here you might also find this answer helpful which essentially follows your approach (and which makes this post regrettably a duplicate).

Generating function approach

Nevertheless I'd like to add another approach based upon generating functions, from which the recurrence relation can be easily derived. It is the so-called Goulden-Jackson Cluster Method.

We consider binary words and the set $B=\{101\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $A(z)$ with the coefficient of $z^n$ being the number of wanted words of length $n$ and derive from it the currence relation.

According to the referred paper (p.7) the generating function $A(z)$ is \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[101]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[101])&=-z^3-z^2\text{weight}(\mathcal{C}[101])\tag{2}\\ \end{align*} where $z^3$ marks the length $3$ of the bad word $101$ and the term $z^2$ respects overlapping of bad words as in $101\color{blue}{01}$.

It follows from (1) and (2): \begin{align*} \color{blue}{A(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2z+\frac{z^3}{1+z^2}}\\ &\,\,\color{blue}{=\frac{1+z^2}{1-2z+z^2-z^3}}\tag{3}\\ \end{align*}

We recall if a generating function has a representation as rational function of the form \begin{align*} A(z)=\sum_{n=0}^\infty a_n z^n=\frac{P(z)}{Q(z)} \end{align*} with $P(z), Q(z)$ polynomials, $\deg Q=q>\deg P$ and \begin{align*} Q(z)=1+\alpha_1 z+\alpha_2 z^2+\cdots + \alpha_q z^q \end{align*} then the coefficients $a_n$ follow the recurrence relation \begin{align*} a_{n+q}+\alpha_1 a_{n+q-1}+\alpha_2 a_{n+q-2}+\cdots +\alpha_q a_{n}=0\qquad\qquad n\geq 0 \end{align*} See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley.

Thanks to this theorem we can derive the recurrence relation from (3) as \begin{align*} a_{n+3}-2a_{n+2}+a_{n+1}-a_{n}=0\qquad\qquad n\geq 0 \end{align*} resp. by shifting the indices we get \begin{align*} \color{blue}{a_n}&\color{blue}{=2a_{n-1}-a_{n-2}+a_{n-3}\qquad\qquad n\geq 3}\tag{4}\\ \color{blue}{a_0}&\color{blue}{=1,a_1=2,a_2=4,a_3=7} \end{align*} in accordance with already given answers. The initial conditions of the recurrence relation follow easily.

Two recurrence relations: Besides (4) another recurrence relation \begin{align*} \color{blue}{s_n=s_{n-1}+s_{n-2}+s_{n-4}\qquad\qquad n\geq 4}\tag{5} \end{align*} is stated by @Mateo. In terms of generating functions we observe that expanding in (3) $A(z)$ with $1+z$ results in \begin{align*} A(z)&=\frac{1+z^2}{1-2z+z^2-z^3}=\\ &=\frac{\left(1+z^2\right)(1+z)}{\left(1-2z+z^2-z^3\right)(1+z)}\\ &=\frac{1+z+z^2+z^3}{\color{blue}{1-z-z^2-z^4}}\tag{6} \end{align*} and the denominator in (6) provides us with the recurrence relation (5).