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$. enter image description here

  • $\begingroup$ 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? $\endgroup$ – Crosby Dec 28 '20 at 4:14
  • $\begingroup$ 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$ $\endgroup$ – Ross Millikan Dec 28 '20 at 4:19
  • $\begingroup$ That makes sense. Thanks for your answer! $\endgroup$ – Crosby Dec 28 '20 at 4:33

Consider the following automaton that accepts the strings not containing AB or BA, enter image description here

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,

enter image description here

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


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.