3
$\begingroup$

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 ?

$\endgroup$

4 Answers 4

Reset to default
2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ oh thanks you , i worked over binary strings in a long time so i wrote $2^{n-3}$ :)).However , i did not understand how you obtain $b_n=5b_{n-1}+a_{n-3}$.If $a_n+b_n=5^n$ ,then $b_n=5^n-a_n=5^n-5a_{n-1}+a_{n-3}$.How did you obtain $b_n=5b_{n-1}+a_{n-3}$ ? $\endgroup$ Commented Apr 10, 2021 at 15:13
  • $\begingroup$ because an $n$ string containing $122$ can come from an $n-1$ string that already includes $122$ by appending one new digit (the factor $5$) or by taking a string that is three shorter and does not include $122$ and appending $122$ to it (the $a_{n-3})$. $\endgroup$ Commented Apr 10, 2021 at 15:30
  • $\begingroup$ oh , thanks , it is my fault. Lastly , is there any technique to find explicit formula for $b_n=b_{n-1}+a_{n-3}$.For example , for $n=50$ , how should i aprroach it ? $\endgroup$ Commented Apr 10, 2021 at 15:39
  • $\begingroup$ I know how to solve it when there is one type of recurrence and one type of recurrence + constant values.However , i have never solve when there are two type of recurrence $\endgroup$ Commented Apr 10, 2021 at 15:43
  • $\begingroup$ In this case you can solve the $a$ recurrence first, then plug the value into the $b$ recurrence. In other cases you regard $(a_i,b_i)^T$ as a column vector and the recurrence equation as involving a $2 \times 2$ matrix. You find the eigenvalues and eigenvectors of the matrix. $\endgroup$ Commented Apr 10, 2021 at 17:58
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Sir , i do not know how to thank you , you are pampering me with these elegant solutions :)) .I think that i hope you never experience corona virus will be the best thanks in nowadays... I hope to be a talented combinator like you. $\endgroup$ Commented Apr 11, 2021 at 18:05
  • $\begingroup$ @Bulbasaur: You're welcome and many thanks for your nice wishes. Keep on grasping interesting mathematical ideas and stay healty. $\endgroup$ Commented Apr 11, 2021 at 19:02
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Wooowwww. Sir ,thank you very much for this beneficial answer , i wish you were my professor. It help me very very much. By the way , i guess there is a typo in the end of the solution of part $a$ , it should have been $a_n=5a_{n-1}-a_{n-3}$ instead of $a_n=5a_{n-2}-a_{n-3}$ . $\endgroup$ Commented Apr 11, 2021 at 11:29
  • $\begingroup$ @Bulbasaur: You're welcome! :-) Many thanks for the hint, typo corrected. $\endgroup$ Commented Apr 11, 2021 at 13:15
  • $\begingroup$ @MarkusScheuer how can weight (C) be found ? Is it the lenght of the bad word ? I am trying to understand but i cannot $\endgroup$ Commented May 6, 2021 at 16:13
  • $\begingroup$ @leonard: You might find this answer helpful, where I've added some details about the derivation of $\text{weight}(C)$. $\endgroup$ Commented May 6, 2021 at 16:42
0
$\begingroup$

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:

enter image description here

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.