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

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.

## 1 Answer

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

• Magnificent! Exactly what I was trying to calculate. I was trying with only '01' whereas the trick is to use both '01','10'. I came across this counting while I was computing something totally different. I will definitely want to acknowledge you and cite this solution whenever I finish that project, if you are ok with it @joriki. Thank you very much. – aNumosh Apr 24 at 21:04
• @aNumosh: That's very kind of you, yes, I would certainly be OK with that. And you're quite welcome. – joriki Apr 24 at 21:05