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)


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.