[seqfan] Lyndon words

Wouter Meeussen wouter.meeussen at telenet.be
Sun Mar 9 01:21:32 CET 2014


In http://oeis.org/A001037  under ‘Example’ and in http://en.wikipedia.org/wiki/Lyndon_word under ‘Enumeration’ we find the binary Lyndon words themselves (not their counts) as
0,1,01,001,011,0001,0011,0111,00001,00011,00101,00111,01011,01111,...
Since each starts with a zero bit, I can see two ways of encoding these as decimal numbers:
either prepend a “1” bit
{2,3,5,9,11,17,19,23,33,35,37,39,43,47,65,67,69,71,75,77,79,87,95,...}
or switch  1’s and 0’s .
{1,0,2,6,4,14,12,8,30,28,26,24,20,16,62,60,58,56,52,50,48,40,32,...}
The first seems more natural, and produces an increasing sequence.
For such sequence, split in runs by bit-count, the number of Lyndon words in each run is A001037.

Would you also prefer the first option, and, if so, how should I name it?

Wouter.



More information about the SeqFan mailing list