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.
Find the number of $n$-length Lyndon words on alphabet $\{0,1\}$ with $k$ blocks of 0’s.
combinatoricscombinatorics-on-wordslyndon-words
Related Solutions
Let $a_n$ be the number of strings of length $n$ where every $1$ is followed by at most $k$ zeroes. There are two cases; either the string has a one, or it doesn't. In the former case, the maximal run of zeroes at the end must be of length at most $k$. Therefore, for all $n>k+1$, $$ a_n = 1+a_{n-1}+a_{n-2}+\dots+a_{n-k-1} $$ As you said, the base cases are $a_n=2^n$ for $n\le k+1$. (Note the base case $a_0=1$, because there is one valid string of length $0$, namely the empty string).
For example, when $k=0$, the recurrence is $a_n=a_{n-1}+1$, which implies $a_n=n+1$. Also, $$ f(4,2) = 1+f(3,2) + f(2,2) + f(1,2) =1+8 + 4 + 2 = 15\\ f(5,2) = 1+f(4,2) + f(3,2) + f(2,2) =1+15+8+4= 28\\ f(6,2) = 1+f(5,2) + f(4,2) + f(3,2) =1+28+15+8= 52 $$
You can even simplify this recurrence a bit more. The recurrence when $n$ is replaced with $n-1$ is $$ a_{n-1} = 1+a_{n-2}+a_{n-3}+\dots+a_{n-k-2}\tag{$n>k+2$} $$ Subtracting these equations $$ \boxed{a_{n}=2a_{n-1}-a_{n-k-2}.} $$
You can compute $a_n$ in $O(k^3\log n)$ time if you are careful. The last recurrence can be written as a matrix equation, which I illustrate when $k=2$: $$ \begin{bmatrix}a_n \\ a_{n-1} \\ a_{n-2} \\a_{n-3}\end{bmatrix}= \begin{bmatrix} 2 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n-1} \\ a_{n-2} \\a_{n-3}\\a_{n-4}\end{bmatrix} $$ Letting $A$ be the $(k+2)\times (k+2)$ matrix, iterating the recurrence implies $$ \begin{bmatrix}a_n \\ a_{n-1} \\ \vdots \\a_{n-k-1}\end{bmatrix}=A^{n-k-2}\begin{bmatrix}a_{k+2} \\ a_{k+1} \\ \vdots \\a_{1}\end{bmatrix} $$ Therefore, you can compute the vector on the left by computing a power of the matrix $A$. Using exponentiation by squaring, this takes only $O(\log n)$ matrix multiplication, each of which naively takes $O(k^3)$ arithmetic operations.
Think of it in a different way. Given binary strings $T$ and $S$ of lengths $n+m$ and $n$ respectively, $T$ can be obtained from $S$ by inserting $m$ characters if and only if $S$ is a subsequence of $T$. Now, when is that true?
If it is, the subsequence can be obtained as follows. Starting at the left, let $i_1$ be the first position $i$ where $T_i = S_1$, let $i_2$ be the first $i > i_1$ where $T_i = S_2$, ..., $i_n$ the first $i > i_{n-1}$ where $T_i = S_n$. If you can define $i_1, \ldots, i_n$ in this way, i.e. you never get to a point where there are no $i > i_{k-1}$ such that $T_i = S_k$, then $S$ is the subsequence $T_{i_1},\ldots, T_{i_n}$.
Now, given two binary strings $S$ and $S'$ of length $n$, I will define a map $f$ from $\{0,1\}^{n+m}$ to itself such that $S$ is a subsequence of $T$ if and only if $S'$ is a subsequence of $f(T)$. Consider the construction above for $T$ and $S$, obtaining $i_1, \ldots, i_k$ (where either $k=n$, in which case $S$ is a subsequence of $T$, or $k < n$ and $i_{k+1}$ does not exist). For convenience, take $i_0 = 0$, and $i_{k+1} = n+m+1$. If $i_{j-1} < i \le i_{j}$, let $f(T)_i = T_i$ if $S_j = S'_j$ (or $j = n+1$), $1-T_i$ if $S_j \ne S'_j$. It is easy to see that $f$ is a one-to-one correspondence and has the desired property. This shows that the number of $T$ with $S$ as a subsequence is equal to the number with $S'$ as a subsequence.
Best 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}