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?
Best Answer
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$.