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.


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}

| cite | improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – aNumosh Apr 24 at 21:04
  • $\begingroup$ @aNumosh: That's very kind of you, yes, I would certainly be OK with that. And you're quite welcome. $\endgroup$ – joriki Apr 24 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.