Finding recurrence relation that contain and do not contain $122$ in the alphabet of $(0,1,2,3,4)$

Question

Lets consider the $n-$ strings over the alphabet $\color{purple}{\{0,1,2,3,4\}}$ that

$\color{blue}{a-)}$ do not contain the substring $\color{green}{122}$ such that $1334211112$ is allowed but $..44311 $$\color{red}{122}$ $344..$ is not allowed.

$\color{blue}{b-)}$ contain the substring $\color{green}{122}$

I am trying to find the recurrence relation of $n$ strings that satisfies the desired conditions respectively.I found recurrence relations but i am not sure whether they are true or not .

$\color{BROWN}{SOLUTION:}$

$\color{blue}{a-)}$ We know that this $n$ lenght strings will end up with either $0$ or $1$ or $2$ or $3$ or $4$.

Lets say that the string ends with $0$ and does not contain $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $1$ and does not contain $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $2$ and does not contain $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $3$ and does not contain $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $4$ and does not contain $122$ , so there are $a_{n-1}$ such strings.

So, there are $5a_{n-1}$ such strings that do not contain $122$ , but let us think about the string which end with $2$ and do not contain $122$. It has $a_{n-1}$ string that do not have $122$ , but this $a_{n-1}$ string might end with $12$. Because of this, we must subtract the sequence which end up with $2$ and have a substring with lengh $n-1$ but end with $12$.

Hence , the solution is $a_n=5a_{n-1}-a_{n-3}$

$\color{blue}{b-)}$ We know that this $n$ lenght strings will end up with either $0$ or $1$ or $2$ or $3$ or $4$.

Lets say that the string ends with $0$ and contains $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $1$ and contains $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $02$ and contains $122$ , so there are $a_{n-2}$ such strings.

Lets say that the string ends with $12$ and contains $122$ , so there are $a_{n-2}$ such strings.

Lets say that the string ends with $022$ and contains $122$ , so there are $a_{n-3}$ such strings.

Lets say that the string ends with $122$ , so there are $5^{n-3}$ such strings.

Lets say that the string ends with $322$ and contains $122$ , so there are $a_{n-3}$ such strings.

Lets say that the string ends with $422$ and contains $122$ , so there are $a_{n-3}$ such strings.

Lets say that the string ends with $32$ and contains $122$ , so there are $a_{n-2}$ such strings.

Lets say that the string ends with $42$ and contains $122$ , so there are $a_{n-2}$ such strings.

Lets say that the string ends with $3$ contains $122$ , so there are $a_{n-1}$ such strings.

Lets say that the string ends with $4$ contains $122$ , so there are $a_{n-1}$ such strings.

$\therefore a_n=4a_{n-1}+4a_{n-2}+3a_{n-3}+5^{n-3}$

Is my solution correct ? Moreover , if you know another approach to this solution , can you share your knowledge with me ?

What's more , do you know any book or website to find these types of exercises to improve myself ?

Answer 1

Here we derive a recurrence relation for (a) and (b) based upon a generating function approach, the so-called Goulden-Jackson Cluster Method.

Case (a):

We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1,2,3,4\}$$ and the set $B=\{122\}$ 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 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=|\mathcal{V}|=5$, 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}[122]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[122])&=-z^3\\ \end{align*}

It follows \begin{align*} \color{blue}{A(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\ &\,\,\color{blue}{=\frac{1}{1-5z+z^3}}\tag{1}\\ \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 (1) as \begin{align*} a_{n+3}-5a_{n+2}+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}{=5a_{n-1}-a_{n-3}}\qquad\qquad n\geq 3\tag{2}\\ \color{blue}{a_0}&\color{blue}{=1, a_1=5, a_2=25} \end{align*} The initial conditions of the recurrence relation (2) follow immediately, since the number of all words of length $n$ from the alphabet $\mathcal{V}=\{0,1,2,3,4\}$ is $5^n$ and the restriction due to the bad word $122$ becomes effective starting with $n=3$ where $a_3=5^3\color{blue}{-1}=124$.

Case (b):

We derive a recurrence relation for all words of length $n\geq 0$ built from the alphabet $$\mathcal{V}=\{0,1,2,3,4\}$$ which do contain the word $122$ with the help from case (a).

Since the number of all words of length $5$ built from the alphabet $\mathcal{V}$ is $5^n$, a generating function $B(z)$ is \begin{align*} \color{blue}{B(z)}&=\sum_{n=0}^\infty b_nz^n=\sum_{n=0}^\infty \left(5^n-a_n\right)z^n\\ &=\sum_{n=0}^\infty 5^nz^n-A(z)\\ &=\frac{1}{1-5z}-\frac{1}{1-5z+z^3}\\ &\,\,\color{blue}{=\frac{z^3}{1-10z+25z^2+z^3-5z^4}}\tag{3} \end{align*}

Thanks to the the theorem above we find from (3) the recurrence relation \begin{align*} b_{n+4}-10b_{n+3}+25b_{n+2}+b_{n+1}-5b_n=0\qquad\qquad n\geq 0 \end{align*} resp. by shifting the indices we get

\begin{align*} \color{blue}{b_n}&\color{blue}{=10b_{n-1}-25b_{n-2}-b_{n-3}+5b_{n-4}}\qquad\qquad n\geq 4\\ \color{blue}{b_0}&\color{blue}{=b_1=b_2=0}\\ \color{blue}{b_3}&\color{blue}{=1} \end{align*} The initial conditions might follow immediately or can be derived from the relation $b_n=5^n-a_n$.

Answer 2

The first is correct. You claim that you can take any $n-1$ string and add any character to it (which gives $5a_{n-1}$) except the ones that end in $122$ (which is the subtraction of $a_{n-3})$. You should give starting conditions $a_0=1,a_1=5,a_2=25$

For the second it would be better not to reuse the notation $a_n$. If we call the number of $n$ strings that include $122$ somewhere $b_n$ we clearly have $a_n+b_n=5^n$. If you don't mind coupled recurrences this gives $b_n=5b_{n-1}+a_{n-3}$. Your statement that the string ends with $122$ gives $2^{n-3}$ is wrong. It should be $5^{n-3}$. You also miss strings that end in $222$, which changes the $3$ coefficient to $4$. Unfortunately the result, $b_n=4(b_{n-1}+b_{n-2}+b_{n-3})+5^{n-3}$ misses strings like $1222$. It doesn't end in $122$ so it is missed by the last term and it doesn't have $122$ somewhere before your additions.

Answer 3

Here we give an answer for the part (a) which can be seen as supplement to OPs nice solution. We use a convenient notation which is helpful to derive the wanted recurrence relation.

We count the number $a_n$ of valid binary strings, i.e. strings which do not contain $122$ by partitioning them according to their matching length with the initial parts of the bad string $122$. \begin{align*} \color{blue}{a_n=a^{[0134]}_n+a^{[2]}_n+a^{[22]}_n}\tag{1} \end{align*}

• The number $a^{[0134]}_n$ gives the number of valid words of length $n$ with left-most character in $\{0,1,3,4\}$.

• The number $a^{[2]}_n$ counts the valid strings of length $n$ which start with left-most character $2$, which is the rightmost character of the bad word $12\color{blue}{2}$.

• The number $a^{[22]}_n$ counts the valid strings of length $n$ which have as left-most characters $22$, which are the two right-most characters of the bad word $1\color{blue}{22}$.

We get a relationship between valid strings of length $n$ with those of length $n+1$ as follows:

• If a word counted by $a^{[0134]}_n$ is appended with a character from $\{0,1,3,4\}$ from the left, it contributes to $a^{[0134]}_{n+1}$. If it is appended by $2$ from the left it contributes to $a^{[2]}_{n+1}$.

• If a word counted by $a^{[2]}_n$ is appended with a character from $\{0,1,3,4\}$ from the left, it contributes to $a^{[0134]}_{n+1}$. If it is appended by $2$ from the left it contributes to $a^{[22]}_{n+1}$.

• If a word counted by $a^{[22]}_n$ is appended with a character from $\{0,1,3,4\}$ from the left, it contributes to $a^{[0134]}_{n+1}$. Appending from the left by $1$ is not allowed since then we have an invalid word starting with $122$.

This relationship can be written as \begin{align*} &\color{blue}{a^{[0134]}_{n+1}=4a^{[0134]}_{n}+4a^{[2]}_{n}+3a^{[22]}_{n}}\tag{2}\\ &\color{blue}{a^{[2]}_{n+1}\ \ =\ \, a^{[0134]}_{n}}\tag{3}\\ &\color{blue}{a^{[22]}_{n+1}\ \ =\qquad\qquad\ \, a^{[2]}_n+a^{[22]}_n}\tag{4} \end{align*}

Note that we have $5$ characters $0,1,2,3,4$ to consider which can be appended to the left and the equations (2) - (4) show $5$ times $a^{[0134]}_{n},a^{[2]}_{n}$ and $4$ times $a^{[22]}_n$ indicating that all different cases are considered.

We can now derive a recurrence relation from (1) - (4):

We obtain for $n\geq 3$: \begin{align*} \color{blue}{a_{n+1}}&=a^{[0134]}_{n+1}+a^{[2]}_{n+1}+a^{[22]}_{n+1}\tag{$ \to (1)$}\\ &=\left(4a^{[0134]}_{n}+4a^{[2]}_{n}+3a^{[22]}_{n}\right)\\ &\qquad +\left(a^{[0134]}_{n}\right)+\left(a^{[2]}_n+a^{[22]}_n\right)\tag{$\to (2),(3),(4)$}\\ &=5a^{[0134]}_{n}+5a^{[2]}_{n}+4a^{[22]}_{n}\\ &=5a_n-a^{[22]}_{n}\tag{$\to (1)$}\\ &=5a_n-\left(a^{[2]}_{n-1}+a^{[22]}_{n-1}\right)\tag{$\to (4)$}\\ &=5a_n-\left(a^{[0123]}_{n-2}\right)-\left(a^{[2]}_{n-2}+a^{[22]}_{n-2}\right)\tag{$\to (3),(4)$}\\ &\,\,\color{blue}{=5a_n-a_{n-2}}\tag{$\to (1)$} \end{align*} in accordance with OP's result.

Answer 4

Taking strings containing $122$ as "qualifying", I identify $4$ states to track for each length of string:

• General non-qualifying strings that doesn't end in $1$ or $12$, quantity "$G$"
• Non-qualifying strings that end in $1$, quantity "$P_1$"
• Non-qualifying strings that end in $12$, quantity "$P_2$"
• Qualifying strings, quantity "$Q$"

Then the transition from one length to the next looks like this:

that is

• $G(n+1) = 4G(n)+3P_1(n)+3P_2(n)$
• $P_1(n+1) = G(n)+P_1(n)+P_2(n)$
• $P_2(n+1) = P_1(n)$
• $Q(n+1) = P_2(n)+5Q(n)$

Non-qualifying strings in general are $G+P_1+P_2$, quantity "NQ", so $P_1(n) = NQ(n-1)$

Then substituting $P_1(n-1) = NQ(n-2)$ for $P_2(n)$ we have

• $G(n+1) = 4G(n)+3P_1(n)+3P_2(n) = 4NQ(n)-NQ(n-1)-NQ(n-2)$
• $P_1(n+1) = NQ(n)$
• $P_2(n+1) = NQ(n-1)$
• $\color{#0b2}{NQ(n+1) = 5NQ(n) - NQ(n-2)}$
• $\color{#0b2}{Q(n+1) = 5Q(n) + NQ(n-2)}$

As you might expect, the number of qualifying strings gradually catches up to the non-qualifying strings and overtakes at $n=87$.