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

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?

• So is it correct? Commented Jul 11, 2022 at 15:21
• Without checking all your work, I would note that $s_1=2$ and $s_2=4$. Commented Jul 11, 2022 at 16:40
• @paw88789 thank you i ve corrected it can you tell me if the reasonning is correct? Commented Jul 11, 2022 at 16:59
• someone can help me? Commented Jul 11, 2022 at 18:11
• From OEIS: A005251, recurrence is $s_n=s_{n-1}+s_{n-2}+s_{n-4}$ Commented Jul 11, 2022 at 20:00

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.

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.

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),$$

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

• This is an approach I tried to use but I didn't manage to. Nice work. Commented Jul 11, 2022 at 23:23
• The formula from the OEIS page can be achieved directly as *0 + (*001 + *111) + *0011. Commented Jul 11, 2022 at 23:36
• @DanielMathias Except that I didn't think of that. Personally, I think that Mateo's use of the intermediate formula to reach the OEIS formula is also nice. Commented Jul 11, 2022 at 23:39
• @X0-user-0X See the Addendum that I have just added to the end of my answer. Commented Jul 12, 2022 at 15:04
• @X0-user-0X "So: $s_{n}=s_{n-1}+s_{n-2}+s_{n-3}$." This is wrong, and should instead be So: $s_{n}=s_{n-1}+s_{n-2}+\color{\red}{s_{n-4}}$. I really can't diagnose where you are making a mistake, unless you dispense with your syntax and instead carefully adopt my syntax. Alternatively, perhaps someone else may be able to parse through your syntax. It could be that if you attempt to convert to my syntax, that during the attempt, you will uncover your error. Commented Jul 12, 2022 at 21:50

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 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, 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}.$$

• +1: Your approach is clearly also valid. Further, your use of the intermediate formula to verify the OEIS formula is nicely done. Commented Jul 11, 2022 at 23:40
• Why did i get $s_n=s_{n−1}+s_{n−2}+s_{n−3}$ with my approach? I really don't understand where i made a mistake. Commented Jul 12, 2022 at 10:54
• Thank for your answer but i don't understand where i am wrong in my answer (i get $n-3$ and not $n-4$) Commented Jul 12, 2022 at 12:18

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).

• Thank a lot for your answer! Commented Jul 12, 2022 at 19:06
• @X0-user-0X: You're welcome! :-) Commented Jul 12, 2022 at 19:06
• I ve tried to correct my reasonning, can you tell me now if it is correct? $s_{n}=s_{n-1}0+s_{n-1,valid}1=s_{n-1}0+s_{n-2,valid}01+s_{n-2,valid}11$ As $s_{n-2,valid}01=s_{n-3}001$ And: $s_{n-2,valid}11=s_{n-4}0011+s_{n-4}1111+s_{n-4,valid}0111=s_{n-4}0011+s_{n-4}1111+s_{n-5}00111$ We finally get: $s_{n}=s_{n-1}0+s_{n-3}001+s_{n-4}0011+s_{n-4}1111+s_{n-5}00111$ In conclusion:$s_{n}=s_{n-1}+s_{n-3}+2s_{n-4}+s_{n-5}$, is it correct now? Commented Jul 12, 2022 at 23:44
• @X0-user-0X: This approach fails also due to $s_{n-4}1111$, since we have valid words of length $n-4$ which end with $10$. We observe this approach fails whenever there is a term starting with $1$ after $s_{n-k}$. So, it is not admissible to simply skip the digits. You need an approach as given in my referred answer. Commented Jul 13, 2022 at 5:04