Counting Lyndon words with no adjacent character repeats I'm interested in counting aperiodic words in bracelets. I know that corresponds to Lyndon words, and I know how to count the number of Lyndon words for an $(n, k)$ bracelet using Moreau's necklace counting function:
$$\frac{1}{n}\sum_{d|n}\mu \left(\frac{n}{d}\right)k^d$$
How could I add the condition that I only want to count words with no adjacent letter repeats? (Example: for $n=3$ and $k \geqslant 3$, $ABC$ would count, but $ABCA$ wouldn't due to the repeating of 'A')
 A: This is somewhat similar to Find the number of $n$-length Lyndon words on alphabet $\{0,1\}$ with $k$ blocks of 0's. and can be solved with the same basic approach.
First we need to count the circular $k$-ary words of length $n$ without adjacent identical letters. This is done using a recurrence relation at In how many ways can we colour $n$ baskets with $r$ colours?. We can also do it using inclusion–exclusion: There are $n$ conditions for the $n$ pairs of neighbours. There are $\binom nj$ ways to choose $j$ particular conditions to violate, and doing so leaves $n-j$ free choices of letters, except for $j=n$, where it leaves $1$ choice, not $0$. Thus by inclusion–exclusion there are
$$
\sum_{j=0}^n\binom nj(-1)^jk^{n-j}+(-1)^n(k^1-k^0)=(k-1)^n+(-1)^n(k-1)
$$
circular $k$-ary words that violate none of the conditions. (This applies for $n\gt1$; obviously for $n=1$ all $k$ Lyndon words have no repeating adjacent characters.)
Now we just have to treat one fundamental period of a word with period $p$ as a circular word of length $p$ and replace the factor $k^d$ in the necklace counting function by our count of admissible necklaces to obtain the count of
$$
\frac1n\sum_{d\mid n}\mu\left(\frac nd\right)\left((k-1)^d+(-1)^d(k-1)\right)\;.
$$
The first term is just the number of Lyndon words / aperiodic bracelets with one fewer letter. The second term sums to $0$ except for $n=1$, which is a special case anyway, and for $n=2$, where it sums to $k-1$. Thus, the number of $k$-ary Lyndon words of length $n$ without repeating adjacent characters is
$$
\begin{cases}
k&n=1\;,\\
\frac{k(k-1)}2&n=2\;,\\
\text{the number of $(k-1)$-ary Lyndon words of length $n$}&n\gt2\;.
\end{cases}
$$
