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.


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.


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

| cite | improve this answer | |

Using the notation given,


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.


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


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.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ I love that method. :) $\endgroup$ – N. Shales Jun 22 '18 at 16:27
  • 1
    $\begingroup$ @N.Shales: Thanks. :-) ... and I also deeply appreciate John Riordan's book. (+1) $\endgroup$ – Markus Scheuer Jun 22 '18 at 17:27

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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.