Find the number of $n$-length Lyndon words on alphabet $\{0,1\}$ with $k$ blocks of 0's.

Question

Let $L(n,k)$ denote the number of Lyndon words of lenth $n$ on a binary alphabet $\{0,1\}$ where $k$ is the number of blocks of 0's in the word. For example, if we consider $n=5$, then 5-length Lyndon words are 00001, 00011, 00101, 00111, 01011, 01111. Among these six words, 00101 and 01011 have two blocks of 0's, so $L(5,2)=2$. Similarly, $L(5,1)=4$. Now I ask to myself is there any moebius inversion type formula so that I can write $L(n,k)$ as a sum of some known function? I was trying to apply the trick used in the solution of this question here, but could not get to the conclusion. Any comment or suggestion would be helpful.

Answer 1

The binary Lyndon words of length $n$ are in bijection with the aperiodic binary necklaces of length $n$, and counting them by inclusion–exclusion on the lattice of divisors of $n$ yields the count

$$ \frac1n\sum_{d\mid n}\mu\left(\frac nd\right)2^d $$

given in the linked question. Here $2^d$ counts the binary necklaces with period $d$. So we need to count the binary necklaces with period $d$ that have $k$ blocks of $0$s (and thus also $k$ blocks of $1$s). Since a period $d$ repeats $\frac nd$ times, such necklaces only exist when $\frac nd\mid k$, so we only need to consider divisors of $\gcd(n,k)$ for the repetition count $\frac nd$. Let’s swap $d$ and $\frac nd$ in the expression above to make it easier to replace $\frac nd$:

$$ \frac1n\sum_{s\mid n}\mu(s)2^\frac ns\;. $$

So we need

$$ \frac1n\sum_{s\mid\gcd(n,k)}\mu(s)a_\frac ns\;, $$

where $a_\frac ns$ is the number of necklaces with period $\frac ns$ and $k$ blocks of $0$s.

It’s easier to consider the boundaries between blocks instead of the blocks. Fix some stretch of $\frac ns$ boundaries between digits as a fundamental period. Since it’s repeated $s$ times, this fundamental period contains $\frac ks$ switches from $0$ to $1$ and $\frac ks$ switches from $1$ to $0$. We can have either type of switch first, for a factor of $2$, and then the type of the remaining switches is determined. The $2\frac ks$ switches can be freely selected from the $\frac ns$ possible boundaries in the fundamental period, so as they can alternate in two ways, there are $2\binom{\frac ns}{2\frac ks}$ ways to select them. This yields a count of

$$ L(n,k)=\frac2n\sum_{s\mid\gcd(n,k)}\mu(s)\binom{\frac ns}{2\frac ks}\;. $$

In your example with $n=5$ and $k=2$, we have $r=\gcd(5,2)=1$, so we only get a single term:

$$ L(5,2)=\frac25\mu(1)\binom{\frac51}{2\cdot\frac21}=\frac25\cdot5=2\;, $$

in agreement with your count. Since that turned out not to be such an interesting example, let’s calculate $L(6,2)$:

\begin{eqnarray} L(6,2) &=& \frac26\sum_{s\mid2}\mu(s)\binom{\frac6s}{\frac4s} \\ &=& \frac13\left(\binom64-\binom32\right) \\ &=& \frac13(15-3) \\ &=& 4\;, \end{eqnarray}

and indeed there are $4$ binary Lyndon words of length $6$ with $2$ blocks of $0$s, namely $000101$, $010111$, $001101$ and $001011$. As a further check, let’s calculate $L(4,2)$:

\begin{eqnarray} L(4,2) &=& \frac24\sum_{s\mid2}\mu(s)\binom{\frac4s}{\frac4s} \\ &=& \frac12\left(\binom44-\binom22\right) \\ &=& 0\;, \end{eqnarray}

and indeed there are no binary Lyndon words of length $4$ with $2$ blocks of $0$s, as the only candidate word is periodic.

Here’s a table of the first few values; note the symmetry when $n$ is a multiple of $4$:

\begin{array}{c|cc} n\setminus k&1&2&3&4&5&6&7&8&9&10\\\hline 1\\ 2&1\\ 3&2\\ 4&3&0\\ 5&4&2\\ 6&5&4&0\\ 7&6&10&2\\ 8&7&16&7&0\\ 9&8&28&18&2\\ 10&9&40&42&8&0\\ 11&10&60&84&30&2\\ 12&11&80&153&80&11&0\\ 13&12&110&264&198&44&2\\ 14&13&140&429&424&143&12&0\\ 15&14&182&666&858&400&60&2\\ 16&15&224&1001&1600&1001&224&15&0\\ 17&16&280&1456&2860&2288&728&80&2\\ 18&17&336&2061&4848&4862&2052&340&16&0\\ 19&18&408&2856&7956&9724&5304&1224&102&2\\ 20&19&480&3876&12576&18475&12576&3876&480&19&0\\ \end{array}