# Count n-length words containing pattern

I have a class $A$ of words from alphabet of letters {a,b,c}, containing "abbc" and class $B$ which has the same words but with length n = 50

a) How to identify generating function of $A$ ? $A=\left \{ x_{1}x_{2}x_{3}x_{4}...\ : \forall{_{1\leq i } \left (x_{i} \in \left \{ a,b,c \right \}\right ) \wedge \exists_{4\leq i}\left ( x_{i-3}x_{i-2}x_{i-1}x_{i}=abbc\right )} \right \}$

b) How to count how many words does $B$ have?

$B= \left \{ x_{1}x_{2}...x_{49-1}x_{50} \ : \forall{_{1\leq i \leq n } \left (x_{i} \in \left \{ a,b,c \right \}\right ) \wedge \exists_{4\leq i \leq 50}\left ( x_{i-3}x_{i-2}x_{i-1}x_{i}=abbc\right )} \right \}$

• Perhaps you will find useful section I.4.2, pag 56 of Analytic Combinatorics of Flajolet and Sedgewick. Jan 11, 2015 at 17:36

b) It seems the following.

For each non-negative integer $n$ let $a(n)$ be the number of words from $A$ (that is, containing a substring “abbc”) of length $n$. Then it is easy to check that the sequence $\{a(n)\}$ satisfies the following recurrence (a*):

$$a(n)=3a(n-1)-a(n-4)+3^{n-4}$$

for all $n\ge 4$ and the initial conditions $a(0)=a(1)=a(2)=a(3)=0$. It is clear that the sequence $\{a(n)\}$ is uniquely determined by the recurrence (a*) and the initial conditions. Unfortunately, it is not contained in The On-Line Encyclopedia of Integer Sequences.

So we shall search the sequence $\{a(n)\}$ in the form $a(n)=b(n)+c(n)$, where $\{b(n)\}$ is the homogeneous part of the solution, that is the sequence $\{b(n)\}$ satisfies the recurrence (b*):

$$b(n)=3b(n-1)-b(n-4)$$

for all $n\ge 4$ and the sequence $\{c(n)\}$ is a partial solution of the recurrence (a*), that is (c*):

$$c(n)=3c(n-1)-c(n-4) +3^{n-4}$$

for all $n\ge 4$, but not necessarily $c(0)=c(1)=c(2)=c(3)=0$.

The c-part of the solution is easy. We shall search the sequence $\{c(n)\}$ in the form $c(n)=c\cdot3^n$ for all $n\ge 0$. Such a sequence will satisfy the recurrence (c*) iff $c=1$. Unfortunately, this sequence does not satisfy the condition $c(0)=c(1)=c(2)=c(3)=0$, so we have to proceed to b-part of the solution, which is much harder.

Consider the characteristic polynomial $p(\lambda)=\lambda^4-3\lambda^3+1$ of the recurrence. The polynomial $p(\lambda)$ is coprime with its derivative $p’(\lambda)= 4\lambda^3-9\lambda^2$, so all the roots of $p(\lambda)$ are distinct. Therefore we may search the sequence $\{b(n)\}$ in the form

$$b(n)=C_1\lambda_1^n+ C_2\lambda_2^n+ C_3\lambda_3^n+ C_4\lambda_4^n,$$

where $\lambda_i$ are the distinct roots of the polynomial $p(\lambda)$ and $C_i$ are real constants. The set of the solutions of the recurrence (b*) is a linear space of the dimension 4, with the basis consisting of the geometric progressions $\{\lambda_1^n\}$, $\{\lambda_2^n\}$, $\{\lambda_3^n\}$, and $\{\lambda_4^n\}$. We search the sequence $\{b(n)\}$ as a linear combination of the basis sequences in order to satisfy the initial conditions. That is we have to satisfy the following system of equations (**):

$\cases{0=b(0)+c(0)=3^0+C_1\lambda_1^0+C_2\lambda_2^0+C_3\lambda_3^0+ C_4\lambda_4^0=1+C_1+C_2+C_3+C_4\\ 0=b(1)+c(1)=3^1+C_1\lambda_1^1+C_2\lambda_2^1+C_3\lambda_3^1+ C_4\lambda_4^1=3+\lambda_1C_1+\lambda_2C_2+\lambda_3C_3+\lambda_4C_4\\ 0=b(2)+c(2)=3^2+C_1\lambda_1^2+C_2\lambda_2^2+C_3\lambda_3^2+ C_4\lambda_4^2=9+\lambda_1^2C_1+\lambda_2^2C_2+\lambda_3^2C_3+\lambda_4^2C_4\\ 0=b(3)+c(3)=3^3+C_1\lambda_1^3+C_2\lambda_2^3+C_3\lambda_3^3+ C_4\lambda_4^3=27+\lambda_1^3C_1+\lambda_2^3C_2+\lambda_3^3C_3+\lambda_4^3C_4}$

Since the determinant of the system is

$$2S=\left|\begin{array}{} 1 & 1 & 1 & 1\\ \lambda_1 & \lambda_2 & \lambda_3 & \lambda_4\\ \lambda_1^2 & \lambda_2^2 & \lambda_3^2 & \lambda_4^2\\ \lambda_1^3 & \lambda_2^3 & \lambda_3^3 & \lambda_4^3\\ \end{array}\right|=\prod_{1\le i<j\le 4}(\lambda_j-\lambda_i)\ne 0$$

(it is so-called Vandermonde determinant), system (**) has a unique solution.

Now going to the numbers. Unfortunately, the polynomial $p(\lambda)$ has no rational roots, so we cannot easily reduce the solution of the quartic equation $p(\lambda)=0$ to a solution of an equation of smaller degree. The equation $p(\lambda)=0$ can be solved analytically in radicals, using Ferrari method. Mathcad calculated the following cumbersome answer:

MATRIX([[3/4+1/12*3^(1/2)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+1/12*6^(1/2)((27(972+12*5793^(1/2))^(1/3)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)-((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)*(972+12*5793^(1/2))^(2/3)-48*((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+81*3^(1/2)*(972+12*5793^(1/2))^(1/3))/(972+12*5793^(1/2))^(1/3)/((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2))^(1/2)], [3/4+1/12*3^(1/2)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)-1/12*6^(1/2)((27(972+12*5793^(1/2))^(1/3)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)-((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)*(972+12*5793^(1/2))^(2/3)-48*((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+81*3^(1/2)*(972+12*5793^(1/2))^(1/3))/(972+12*5793^(1/2))^(1/3)/((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2))^(1/2)], [3/4-1/12*3^(1/2)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+1/12*I*((-162*(972+12*5793^(1/2))^(1/3)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+6*((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)*(972+12*5793^(1/2))^(2/3)+288*((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+486*3^(1/2)*(972+12*5793^(1/2))^(1/3))/(972+12*5793^(1/2))^(1/3)/((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2))^(1/2)], [3/4-1/12*3^(1/2)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)-1/12*I*((-162*(972+12*5793^(1/2))^(1/3)((27(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+6*((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)*(972+12*5793^(1/2))^(2/3)+288*((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2)+486*3^(1/2)*(972+12*5793^(1/2))^(1/3))/(972+12*5793^(1/2))^(1/3)/((27*(972+12*5793^(1/2))^(1/3)+2*(972+12*5793^(1/2))^(2/3)+96)/(972+12*5793^(1/2))^(1/3))^(1/2))^(1/2)]])

Numerical solution (using LaGuerre method) of the equation $p(\lambda)=0$ yields the roots approximations $2.9615$, $0.76483$, and $-0.36316\pm 0.55642i$. Numerically solving system (**), we obtain an approximation

$$a(n)\simeq 3^n – 1.13484(2.9615)^n +0.41898(0.76483)^n -(0.14207-0.14016i)(-0.36316+0.55642i)^n-(0.14207+0.14016i)(-0.36316-0.55642i)^n.$$

Since the last three exponents are quickly vanishing, I expect that the exact value of $a(n)$ can be obtained by rounding the sum of just two terms with the highest exponent.