Skip to main content
2 of 7
added 283 characters in body
Max Alekseyev
  • 34.6k
  • 5
  • 74
  • 154

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 and 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 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 n} L_{k,m}$$ and (by Möbius inversion) $$L_{n,m} = \sum_{k\mid n} \mu(n/k) E_{k,m}.$$

To compute $E_{n,m}$, let $Z_n(a_1,a_2,\dots)=\frac{1}{n}\sum_{k\mid n} \varphi(k)a_k^{n/k}$ be the cycle index of the cyclic group $C_n$. Then $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) (t^{kd_a}+t^{kd_b})^{n/k}.$$

Max Alekseyev
  • 34.6k
  • 5
  • 74
  • 154