Generating series for ternary strings without 000 and not ending with 0

Question

I would like to find a formula for $T_n$, the number of ternary strings of length $n$ so that they do not contain three consecutive zeroes, and they do not end with $0$ as well. I can find a recurrence relation for $T_n$, however I wonder if we can express $T_n$ as a coefficient of a generating series. Thanks for any help!

Answer 1

I see that you work over recurrence relations , and you are willing to learn. Hence , i will share a very powerful method with you. You can handle nearly all recurrence relation problems with it. Our method is Goulden -Jackson- Cluster Method . I put that link for you , you can read it to learn detaily.

Lets turn to our question. We can claim that $\color{red}{|}$the number of strings that do not have three consecutive zeros$\color{red}{|}$ = $\color{blue}{|}$ the number of strings that do not have three consecutive zeros and end up with $0$$\color{blue}{|}$ + $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $1$ $\color{red}{|}$ + $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $2$ $\color{red}{|}$.

Here , we are looking for $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $1$ $\color{red}{|}$ + $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $2$ $\color{red}{|}$. Right ?

We can see that the number of strings of length $n$ that do not have three consecutive zeros and end up with $1$ is equal to the number of strings of length $(n-1)$ that do not have three consecutive zeros. It is also valid for the string that ends up with $2$.

Now , it is the time for using our powerful method. We will find a generating function and convert it into a sequence of length $(n-1)$.

Lets first calculate for the string end up with $1$ and do not have $3$ consecutive zeros.We said that it is equal to the number of string of length $n-1$ that does not have three consecutive zeros.

We know that our alphabet consists of $3$ elements such as $V=\{0,1,2\}$ , and our bad word is $\{000\}$.

According to the paper $(p.7)$ the generating function $A(z)$ is $$A(z)=\frac{1}{1-dz - \text{weight}(c)}$$

with $d=|V|=3$, the size of the alphabet and $C$ the weight-numerator of bad words with $$\text{weight(c)}= \text{weight}([000])$$

$$\text{weight}([000])= -z^3 - (z^2 +z)\text{weight}([000])$$

$$\text{A(z)}= \frac{1}{1-3z + \frac{z^3}{1+z+z^2}}$$

$$\text{A(z)}= \frac{1+z+z^2}{1-2z-2z^2 -2z^3}$$

We also obtain the same result for the string end up with $2$. Then , the sum of them will give us the generating function for them.Namely , $$\frac{2+2z+2z^2}{1-2z-2z^2 -2z^3}$$

Now , we should convert it into recurrence relation by 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*}

Then , our recurrence relation is $$a_{n-1}=2a_{n-2}+2a_{n-3}+2a_{n-4}$$

Calculation via wolfram

It means that for $n=4$ , there are $52$ such strings , for $n=5$ , there are $152$ such strings , for $n=15$ , the answer is $6843168$ ,so on..

Answer 2

We can describe the set of valid strings as the strings built from the alphabet $V=\{0,1,2\}$ which contain at most one or two consecutive $0$'s and do not end with a $0$.

A regex: We consider strings

• starting with zero or more $1$s or $2$s:$\qquad\quad(1|2)^*$

• followed by zero or more occurrences of $0$ or $00$ each followed by one or more $1$s or $2$s: $$(0(1|2)^+|00(1|2)^+)^*$$

We obtain a regular expression describing all valid words: \begin{align*} \color{blue}{(1|2)^*(0(1|2)^+|00(1|2)^+)^*}\tag{1} \end{align*}

Note these words end with either $1$ or $2$ but not with $0$ as required.

Generating function: $T(z)$:

The regular expression (1) generates all valid words in a unique manner. In such cases we can use it to derive a generating function $$\color{blue}{T(z)=\sum_{n=0}^\infty T_n z^n}$$ with $T_n$ giving the number of valid words of length $n$.

In order to do so all we need to know is the geometric series expansion since the $star$ operator \begin{align*} a^*&=\left(\varepsilon|a|a^2|a^3|\cdots\right)&\text{ translates to } &1+z+z^2+z^3+\cdots=\frac{1}{1-z}\\ (a|b)^*&=\left(\varepsilon|(a|b)|(a|b)^2|(a|b)^3|\cdots\right)&\text{ translates to } &1+2z+4z^2+8z^3+\cdots=\frac{1}{1-2z}\\ \end{align*}

Accordingly $a^+=aa^*$ translates to $\frac{z}{1-z}$ and alternatives like $(\varepsilon|a|aa)$ can be written as $1+z+z^2$.

We obtain from (1) by translating the regular expression in the language of generating functions (and by mixing up somewhat the symbolic to provide some intermediate steps)

\begin{align*} \color{blue}{(1|2)^*(0(1|2)^+|00(1|2)^+)^*} &\longrightarrow \quad \frac{1}{1-2z}\left(\left.\frac{2z^2}{1-2z}\right|\frac{2z^3}{1-2z}\right)^*\\ &\longrightarrow \quad \frac{1}{1-2z}\left(\frac{2z^2+2z^3}{1-2z}\right)^*\\ &\longrightarrow \quad \frac{1}{1-2z}\cdot\frac{1}{1-\frac{2z^2+2z^3}{1-2z}}\\ &\quad\quad\color{blue}{=\frac{1}{1-2z-2z^2-2z^3}} \end{align*}

We conclude: The number of valid words is given by the generating function $T(z)$ \begin{align*} \color{blue}{T(z)}&\color{blue}{=\frac{1}{1-2z-2z^2-2z^3}}\tag{2}\\ &=1+2z+6z^2+18z^3+\color{blue}{52}z^4+152z^5+444z^6+1\,296z^7\cdots \end{align*}

The expansion was done with the help of Wolfram Alpha. We see that e.g. the number of valid words of length $4$ is $\color{blue}{52}$.

Coefficients $T_n$:

We can now calculate $T_n$ from $T(z)$. In order to do so it's convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. We obtain from (2) \begin{align*} \color{blue}{T_n}&=[z^n]\frac{1}{1-2z\left(1+z+z^2\right)}\\ &=[z^n]\sum_{k=0}^{\infty}(2z)^k\left(1+z+z^2\right)^k\tag{3.1}\\ &=\sum_{k=0}^n2^k[z^{n-k}]\left(1+z(1+z)\right)^k\tag{3.2}\\ &=\sum_{k=0}^n2^{k}[z^{n-k}]\sum_{l=0}^{k}\binom{k}{l}z^l(1+z)^{l}\tag{3.3}\\ &=\sum_{k=0}^n2^{k}\sum_{l=0}^{\min\{k,n-k\}}\binom{k}{l}[z^{n-k-l}](1+z)^{k}\tag{3.4}\\ &\,\,\color{blue}{=\sum_{k=0}^n2^{k}\sum_{l=0}^{\min\{k,n-k\}}\binom{k}{l}\binom{k-l}{n-k-l}}\tag{3.5} \end{align*}

Comment:

• In (3.1) we use the geometric series expansion.

• In (3.2) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and set the upper limit of the sum to $n$ since other values do not contribute.

• In (3.3) we apply the binomial theorem.

• In (3.4) we use again the rule as in (3.2) and restrict the upper limit since the coefficient of operator has non-negative exponents of $z$ only.

• In (3.5) we select the coefficient of $[z^{n-k-l}]$.

Example $T_4$:

We use (3.5) to calculate exemplarily $T_4$. We obtain \begin{align*} \color{blue}{T_4}&=\sum_{k=0}^{4}2^k\sum_{l=0}^{\min\{k,4-k\}}\binom{k}{l}\binom{l}{4-k-l}\\ &=\sum_{l=0}^0\binom{0}{l}\binom{l}{4-l}+2\sum_{l=0}^1\binom{1}{l}\binom{l}{3-l}+4\sum_{l=0}^2\binom{2}{l}\binom{l}{2-l}\\ &\qquad\quad+8\sum_{l=0}^1\binom{3}{l}\binom{l}{1-l}+16\sum_{l=0}^0\binom{4}{l}\binom{0}{0-l}\\ &=0+0+4\left(\binom{2}{1}\binom{1}{1}+\binom{2}{2}\binom{2}{0}\right)+8\binom{3}{1}\binom{1}{0}+16\binom{4}{0}\binom{0}{0}\\ &=0+0+4\cdot3+8\cdot3+16\cdot1\\ &\,\,\color{blue}{=52}\\ \end{align*} as expected.