At Counting Lyndon words with no adjacent character repeats, it turned out that for $n\ge3$ the number of $k$-ary Lyndon words of length $n$ without adjacent identical letters is the number of $(k-1)$-ary Lyndon words of length $n$. I suspect there should be an elegant combinatorial proof of this.
Without the aperiodicity constraint of the Lyndon words, the number of circular arrangements of $n$ letters from an alphabet of size $k$ without adjacent identical letters is
$$ (k-1)^n+(-1)^n(k-1)\;. $$
It’s not surprising that this is roughly $(k-1)^n$, since as you go around the circle, you can choose each letter freely except it can’t be the same as the previous one. What is surprising (to me), though, is that the boundary effect when you get back to the origin doesn’t quite cancel for unconstrained circular arrangements (leaving the term $(-1)^n(k-1)$), but does cancel exactly for aperiodic ones. In the algebraic derivation of the result, this happens because the Dirichlet convolution of $(-1)^n$ with the Möbius function is zero except at $n=2$; but I don’t know what that corresponds to combinatorially.
One idea I had was to use the fact that a Lyndon word is lexicographically minimal among its rotations, which means that an aperiodic Lyndon word can’t start and end with the same letter (since otherwise you could rotate the last letter to the front, contradicting minimality). This could somehow make the boundary condition work out right when you look at the choices letter by letter.
Another approach I tried was to treat the letters as residues modulo $k$ and consider the differences between neighbours instead of the values themselves. Then the constraint is that no difference must be $0$, and the differences must add up to $0$. Each admissible arrangement of differences corresponds to $k$ arrangements of letters. But I don’t see how to make that work, either.
My questions are:
- Is there a natural bijection between the $k$-ary Lyndon words of length $n$ without adjacent identical letters and the $(k-1)$-ary Lyndon words of length $n$?
- Or is there some other combinatorial argument why there should be the same number of each?