Enumeration
The Lyndon words over the two-symbol binary alphabet {0,1}, sorted by length and then lexicographically within each length class, form an infinite sequence that begins
- ε, 0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...
Here, ε denotes the empty string. The first string that does not belong to this sequence, "00", is omitted because it is periodic (it consists of two repetitions of the substring "0"); the second omitted string, "10", is aperiodic but is not minimal in its permutation class as it can be cyclically permuted to the smaller string "01".
The numbers of binary Lyndon words of each length, starting with length zero, form the integer sequence
- 1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, ... (sequence A001037 in OEIS).
Lyndon words correspond to aperiodic necklace class representatives and can thus be counted with Moreau's necklace-counting function.
Read more about this topic: Lyndon Word