# Number of Lyndon words of given weight

Consider the alphabet consisting of two letters $a$ and $b$, and put the lexicographic order in which $a<b$.

We say that a non-empty word $w$ in this alphabet is a Lyndon word if, for any non-trivial decomposition $w=uv$, one has $u<v$.

Now assume that $a$ and $b$ are given weights $d_a$ and $d_b$, and that the weight of a word is the sum of the letters appearing on it.

Does someone know a formula for the number of Lyndon words of given weight?

A Lyndon word can be characterized as the lexicographically smallest word among its cycle rotations. Hence, Lyndon words can be viewed as (representatives of) equivalence classes of non-periodic words w.r.t. cyclic rotations. Then for enumeration of equivalent classes and Lyndon words with a given weight, we can employ PET as follows.

Let $E_{n,m}$ be the number of equivalence classes of words (both periodic and non-periodic) of length $n$ and weight $m$. Similatly, let $L_{n,m}$ be the number of Lyndon words of length $n$ and weight $m$. Then $$E_{n,m} = \sum_{k\mid \gcd(n,m)} L_{n/k,m/k}$$ and (using Möbius inversion) $$L_{n,m} = \sum_{k\mid \gcd(n,m)} \mu(k)\cdot E_{n/k,m/k}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. By PET, $E_{n,m}$ equals the coefficient of $t^m$ in $$Z_n(t^{d_a}+t^{d_b},t^{2d_a}+t^{2d_b},\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)\cdot (t^{kd_a}+t^{kd_b})^{n/k}.$$

It further follows that $L_{n,m}$ equals the coefficient of $t^m$ in $$\sum_{q\mid \gcd(n,m)} \mu(q)\cdot \frac{q}{n}\sum_{k\mid n/q} \varphi(k)\cdot (t^{qkd_a}+t^{qkd_b})^{n/(qk)}$$ $$= \frac{1}{n} \sum_{p\mid n} (t^{pd_a}+t^{pd_b})^{n/p} \sum_{q\mid \gcd(p,m)} \mu(q)\cdot q\cdot \varphi(p/q).$$ (here $p$ stands for $qk$)

UPDATE. From the generating functins above, we can derive explicit formulae (assuming $d_a<d_b$, without loss of generality): $$E_{n,m} = \frac{1}{n}\sum_{k\mid \gcd(n,m)} \varphi(k)\cdot \binom{\frac{n}{k}}{\frac{m-nd_a}{k(d_b-d_a)}}$$ and \begin{split} L_{n,m} &= \frac{1}{n} \sum_{p\mid \gcd(n,m)} \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}} \sum_{q\mid p} \mu(q)\cdot q\cdot \varphi(p/q) \\ &=\frac{1}{n} \sum_{p\mid \gcd(n,m)} \mu(p)\cdot \binom{\frac{n}{p}}{\frac{m-nd_a}{p(d_b-d_a)}}. \end{split}

(where the binomial coefficients are zero whenever the lower index is negative or fractional)

• Fantastic! I guess these must also have nice Lambert and Dirichlet generating series. Sep 2 '16 at 9:54