Skip to main content
3 of 4
corrected definition
Max Alekseyev
  • 34.6k
  • 5
  • 74
  • 154

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?

barry
  • 51
  • 2