Recurrence for Number of Words of Length $r$ over $[n]$ with no three consecutive letters the same

Question

Let $b_{n,r}$ be the number words of length $r$ over $[n]=\{1,2,\dotsc, n\}$ with no three consecutive letters the same. Show that $$ b_{n,r}=(n-1)(b_{n,r-1}+b_{n,r-2})\quad (r>2) $$ with initial conditions $b_{n,1}=n$ and $b_{n, 2}=n^2$

This question is from Riordan's Introduction to Combinatorial Analysis.

Context

It is stated as a hint in the problem to consider those sequences in the question with a given element first (call these $b_{n,r}^\star$) and a given pair of elements first (call these $b_{n,r}^{\star\star}$) and derive a system of recurrences with $b_{n,r}$.

Earlier I solved the corresponding problem (of no two consecutive letters the same) with correpsonding sequences $a_{n,r}$ and $a_{n,r}^\star$ (those sequences with a given element first) and derived the recurrences $$ \begin{align} a_{n,r}&=na_{n,r}^\star\\ a_{n,r}^\star&=(n-1)a_{n,r-1}^\star \end{align} $$ which imply that $a_{n,r}=n(n-1)^{r-1}$. This question is supposed to generalize this kind of method.

My Attempt

With notation discussed as before I was able to deduce that $$ \begin{align} b_{n,r}&=nb_{n,r}^\star\\ b_{n,r}^\star&=(n^2-1)b_{n,r-1}^\star \end{align} $$ since for the first position there are $n$ choices. Further, Once a given element is first, there are $n^2-1$ pairs that can follow.

And here is where my doubts begin. For $b_{n,r}^{\star\star}$, there is no nice analysis can be done since beginning a sequence with $00$ and $01$ need two separate analyses.

Also it seems that unlike in the previous problem the derived sequence $b_{n,r}^{\star\star}$ is not independent of choice of the given pair to start with.

Any help with an attempt using the context is preferred but other solutions are welcome as well.

4 Answers

I would let $c_{n,r}$ be the number of words of length $r$ with not three consecutive letters the same and not ending in two letters the same and $d_{n,r}$ be the number of words of length $r$ with not three consecutive letters the same and ending in two letters the same. We can then write coupled recurrences $$c_{n,r}=(n-1)(c_{n-1,r}+d_{n-1,r})\\ d_{n,r}=c_{n-1,r}$$ because given a $c$ or a $d$ we can add a letter different from the last to get a $c$. Given a $c$ we can add a matching letter to get a $d$. Then $$\begin {align}b_{n,r}&=c_{n,r}+d_{n,r}\\&=(n-1)(c_{n-1,r}+d_{n-1,r})+c_{n-1,r}\\ &=(n-1)c_{n-1,r}+(n-1)c_{n-2,r}+(n-1)(c_{n-2,r}+d_{n-2,r})\\ &=(n-1)c_{n-1,r}+(n-1)c_{n-2,r}+(n-1)(d_{n-1,r}+d_{n-2,r})\\ &=(n-1)(b_{n-1,r}+b_{n-2,r}) \end {align}$$

Using the notation given,

$$b^\star_{n,r}=(n-1)(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})\tag{1}$$

because a sequence that begins with exactly one copy of a particular letter may be followed by a sequence beginning with either exactly 1 copy or 2 copies of the $n-1$ remaining letters.

Also

$$b^{\star\star}_{n,r}=(n-1)(b^\star_{n,r-2}+b^{\star\star}_{n,r-2})\, ,\tag{2}$$

using similar reasoning for sequences beginning with exactly two copies of a particular letter.

Now since there are $n$ possible first letters we have

$$b_{n,r}=n(b^\star_{n,r}+b^{\star\star}_{n,r})\tag{3}$$

total valid sequences.

We can use $(1)$, $(2)$ and $(3)$ to give

$$\begin{align}b_{n,r}&=n(b^\star_{n,r}+b^{\star\star}_{n,r})\\[1ex] &=n((n-1)(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})+(n-1)(b^\star_{n,r-2}+b^{\star\star}_{n,r-2}))\\[1ex] &=(n-1)(n(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})+n(b^\star_{n,r-2}+b^{\star\star}_{n,r-2})\\[1ex] &=(n-1)(b_{n,r-1}+b_{n,r-2})\, .\tag*{$\blacksquare$}\end{align}$$

By the way: that is an incredible book in my opinion! I highly recommend the two chapters on rook polynomials.

Since other approaches are also welcome here is a technique called Goulden-Jackson Cluster Method which gives us a generating function from which we can derive the wanted recurrence relation.

We consider the words of length $r\geq 0$ built from an alphabet $$[n]=\{1,2,3,\ldots,n\}$$ and the set $B=\{111,222,333,\ldots,nnn\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function \begin{align*} B_n(s)=\sum_{j=0}^\infty b_{n,j} s^j\qquad\qquad n\geq 1 \end{align*} with the coefficient of $s^r$ being the number of searched words of length $r$.

According to the paper (p.7) the generating function $B_n(s)$ is \begin{align*} B_n(s)=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=n$, the size of the alphabet and $\mathcal{C}$ the weight-numerator with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[111])+\text{weight}(\mathcal{C}[222])+\cdots+\text{weight}(\mathcal{C}[nnn]) \end{align*} We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[kkk])&=-s^3-\text{weight}(\mathcal{C}[kkk])(s+s^2)\qquad\qquad 1\leq k\leq n\\ \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[kkk])=-\frac{s^3}{1+s+s^2}\qquad\qquad 1\leq k\leq n\\ \end{align*} from which \begin{align*} \text{weight}(\mathcal{C})&=\sum_{k=1}^n\text{weight}(\mathcal{C}[kkk]) =-\frac{ns^3}{1+s+s^2}\\ \end{align*} follows.

$$ $$

We obtain from (1) for $n\geq 2$ \begin{align*} \color{blue}{B_n(s)}&=\sum_{j=0}^\infty b_{n,j}s^j\\ &=\frac{1}{1-ds-\text{weight}(\mathcal{C})}\\ &=\left(1-ns+\frac{ns^3}{1+s+s^3}\right)^{-1}\\ &\color{blue}{=\frac{1+s+s^2}{1-(n-1)s-(n-1)s^2}}\tag{2}\\ &=1+ns+n^2s^2+n(n^2-1)s^3+n(n^3-2n+1)s^4+\cdots \end{align*}

where the last line was calculated with the help of Wolfram Alpha.

$$ $$

We can derive the recurrence relation from (2) by multiplication with the denominator \begin{align*} B_n(s)(1-(n-1)s-(n-1)s^2)&=1+s+s^2\tag{3}\\ \end{align*} from which by extraction of the coefficient of $s^r\,(r>2)$ \begin{align*} \color{blue}{b_{n,r}-(n-1)b_{n,r-1}-(n-1)b_{n,r-2}=0} \end{align*} follows.

Using the Soup and Croutons diagram - an explanation of the GJ theory

This automaton produces strings with multiplicities. However, the multiplicities will be recorded in the generating function. For example, the cluster 11111 is generated with multiplicity 8 but will be exactly recorded as $1 + 3t +3t^2 + t^3$ in the "at least" generating function.

1. 1 1 1 1 1 has no t
2. 111 1 1 - at least one bad 111 (in first position)
3. 1 111 1 - at least one bad 111 (in the second position)
4. 1 1 111 - at least one bad 111 (in the third position)
5. 111 1 1 - at least two bad 111's (in first and second positions)
6. 111 11 - at least two bad 111's (in first and third positions)
7. 1 111 1 - at least two bad 111's (in second and third positions)

8. 111 1 1 - all three bad 111's

   $$C_k = k^3t + (k + k^2)tC_k$$ hence each $C_k$ has the generating function

   $$ \frac {s^3t} {1 - st - s^2t}$$

By diagram we have $$S = 1 + nsS + nCS$$ so the generating function for S is

$$ \frac 1 { 1 - ns - n \frac {s^3t} {1 - st - s^2t} }$$

By Goulden-Jackson PIE, we have $Exact(t) = AtLeast(t-1)$ and we are interested in $Exact(0)$ so we take $t = -1$ in previous and we obtain the expected - previously presented - result.