# How many $k$-letter words are there such that the letters A and B are not next to each other?

I spent the better part of a long car ride today thinking about the following problem:

Consider an alphabet of $$n$$ letters. How many $$k$$-letter words of this alphabet are there such that two certain letters (say A and B) are not next to each other? A word may contain the same letter multiple times.

My thoughts: There are $$n^k$$ words with length $$k$$ over the alphabet. We need to find and subtract away the number of words where A and B are next to each other. I modeled any such word as one with the string AB or BA at an index $$i$$:

$$x_1x_2x_3\cdots x_{i-1}ABx_{i+2}\cdots x_k$$

The $$x_j$$ here are all letters of the alphabet. We can think of the above word as an $$(i-1)$$-letter word, followed by AB, followed by a $$(k-i-2)$$-letter word. Thus, there are $$n^i \cdot n^{k-i-2} = n^{k-2}$$ words where AB or BA is at an arbitrary index $$i$$. Summing over all $$i$$, we get that there are $$(k-2)n^{k-2}$$ words containing AB and $$2(k-2)n^{k-2}$$ words containing AB or BA. Our final expression for the number of $$k$$-letter words such that A and B are not adjacent is

$$n^k - 2(k-2)n^{k-2}$$

There’s an issue though. I’m over-counting words that contain AB or BA by a lot. I ran a simulation, and at $$n=k=10$$, for example, the correct value is $$8441614754$$, and my answer is $$8400000000$$. By this method, any word that contains AB or BA more than once is counted more than once. Is there any way I can modify this approach to yield the correct result? If not, how should I proceed?

You can handle this with coupled recurrences. Let $$A(k)$$ be the number of words without $$AB$$ or $$BA$$ that end in a character other than $$A$$ or $$B$$. Let $$B(k)$$ be the number of words without $$AB$$ or $$BA$$ that end in $$A$$ or $$B$$. You can add any character to an $$A(k)$$ word, but only $$n-1$$ characters to a $$B(k)$$ word, one of which leaves it as a $$B(k+1)$$ word. The recurrences are $$A(k+1)=(n-2)A(k)+(n-2)B(k)\\ B(k+1)=2A(k)+B(k)\\ A(0)=1\\ B(0)=0$$ For small $$k$$ you can make a spreadsheet to do these. For large $$k$$ you can do the eigenvalue/eigenvector thing on the matrix $$\begin {pmatrix} n-2&n-2\\2&1 \end {pmatrix}$$ The leading eigenvalue is $$\frac 12\left(\sqrt{n^2+2n-7}+n-1\right)\approx n$$ when both $$k$$ and $$n$$ are large. You want $$A(k)+B(k)$$ I made a spreadsheet for $$n=10$$, shown below. In the line for $$n=2$$ the $$98$$ under $$A+B$$ shows there are $$98$$ two character strings that are not $$AB$$ or $$BA$$. As there are $$10^2=100$$ unrestricted strings and we rule out $$2$$, this is correct. The $$18\ B$$ strings have one of $$9$$ characters (not a $$B$$) then an $$A$$, or one of $$9$$ characters (not an $$A$$) then a $$B$$.

• I'm a little confused as to how you came up with the recurrences. What do you mean when you say that you can add any character to an $A(k)$ word, but only $n-1$ characters to a $B(k)$ word? Dec 28, 2020 at 4:14
• Because a $B(k)$ word ends in $A$ or $B$ there is one character you can't add without the word becoming unacceptable. Because the $A(k)$ words do not end with $A$ or $B$, no addition will result in an $AB$ or $BA$ Dec 28, 2020 at 4:19
• That makes sense. Thanks for your answer! Dec 28, 2020 at 4:33

Consider the following automaton that accepts the strings not containing AB or BA,

From the DFA, using Chomsky-Schutzemberger method, we get, $$q_0 = 1+xq_1+xq_2+(n-2)xq_0$$ $$q_1 = 1+xq_1+(n-2)xq_0$$ $$q_2 = 1+xq_2+(n-2)xq_0$$ (We omit $$q_3$$ and $$q_4$$ because it is a dead state)

On solving the above equations (i.e. substituting $$q_1$$ and $$q_2$$) we get the following expression for $$q_0$$, $$q_0 = \frac{1+x}{1-(n-1)x-(n-2)x^{2}}$$ This is our generating function. The coefficient of $$x^{k}$$ gives the number of strings of length k not having AB or BA. For example, for $$n = k = 10$$, Wolfram Alpha gives the following Taylor Series,

And as you can see, the coefficient of $$x^{10}$$ is equal to the answer you have provided.

This answer is based upon the Goulden-Jackson Cluster Method. We consider words of length $$k\geq 0$$ built from an alphabet $$\mathcal{V}$$ with $$|\mathcal{V}|=n$$ and the set $$B=\{AB,BA\}$$ of bad words, which are not allowed to be part of the words we are looking for.

We derive a generating function $$A_n(z)$$ with the coefficient of $$z^k$$ being the number of wanted words of length $$k$$. According to the paper (p.7) the generating function $$A_n(z)$$ is \begin{align*} A_n(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})} \end{align*} with $$d=|\mathcal{V}|=n$$, the size of the alphabet and $$\mathcal{C}$$ the weight-numerator with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[AB])+\text{weight}(\mathcal{C}[BA]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[AB])&=-z^2-\text{weight}(\mathcal{C}[BA])z\\ \text{weight}(\mathcal{C}[BA])&=-z^2-\text{weight}(\mathcal{C}[AB])z\\ \end{align*} and get

\begin{align*} \text{weight}(\mathcal{C}[AB])=\text{weight}(\mathcal{C}[BA])=-\frac{z^2}{1+z} \end{align*}

It follows \begin{align*} \color{blue}{A_n(z)}&=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-nz+2\frac{z^2}{1+z}}\\ &\,\,\color{blue}{=\frac{1+z}{1-(n-1)z-(n-2)z^2}}\tag{1} \end{align*}

Denoting with $$[z^k]$$ the coefficient of $$z^k$$ of a series, we obtain from (1) the number of valid words of length $$k$$ as \begin{align*} \color{blue}{[z^k]}\color{blue}{A_n(z)}&=[z^k]\frac{1+z}{1-(n-1)z-(n-2)z^2}\\ &=[z^k]\sum_{j=0}^\infty z^j\left((n-1)+(n-2)z\right)^j(1+z)\\ &=\sum_{j=0}^k[z^{k-j}]\left((n-1)+(n-2)z\right)^{j}(1+z)\\ &=\sum_{j=0}^k[z^j]\left((n-1)+(n-2)z\right)^{k-j}(1+z)\\ &\,\,\color{blue}{=\sum_{j=0}^k\binom{k-j}{j}(n-2)^j(n-1)^{k-2j}}\\ &\qquad\qquad\color{blue}{+\sum_{j=1}^k\binom{k-j}{j-1}(n-2)^{j-1}(n-1)^{k-2j+1}}\tag{2} \end{align*}

Plausibility check: Evaluating (2) at $$n=k=10$$ we obtain \begin{align*} [z^{10}]A_{10}(z)=8\ 441\ 614\ 754 \end{align*} in accordance with OPs calculation.