4
$\begingroup$

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')

$\endgroup$
4
  • $\begingroup$ I think where you have $2^d$ you mean $k^d$? (You don't mention a restriction to binary anywhere.) $\endgroup$
    – joriki
    Apr 25, 2020 at 19:37
  • $\begingroup$ You can get properly sized parentheses (and other paired delimiters) that adjust to the size of their content by preceding them with \left and \right. $\endgroup$
    – joriki
    Apr 25, 2020 at 22:01
  • $\begingroup$ Thanks all, corrected $\endgroup$
    – occulus
    Apr 25, 2020 at 23:17
  • $\begingroup$ I posted a question about a combinatorial proof of the unexpectedly simple result here. $\endgroup$
    – joriki
    Apr 26, 2020 at 13:49

1 Answer 1

2
$\begingroup$

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} $$

$\endgroup$
1
  • 1
    $\begingroup$ Thanks joriki. Wow, what an elegant result! $\endgroup$
    – occulus
    Apr 27, 2020 at 8:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .