Return to Question

Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner's and my Hopf algebras in Combinatorics. If you are not a stranger to combinatorics on words, scroll right down to the question.

Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner's and my Hopf algebras in Combinatorics. If you are not a stranger to combinatorics on words, scroll right down to the question.

Each of the Conjectures 1 and 2 would imply that the number of Nyldon words of given length over a given alphabet equals the number of Lyndon words of the same data.

Each of the Conjectures 1 and 2 would imply that the number of Nyldon words of given length over a given alphabet equals the number of Lyndon words of the same data. This is, in fact, equivalent to Conjecture 1 (because one can WLOG assume $\mathfrak A$ finite, and then argue using the fact that surjections between finite sets of equal size must be injections), so Conjecture 2 can be regarded as a stronger version of Conjecture 1.

length $1$: the words $0$ and $1$.

length $2$: the word $10$.

length $3$: the words $100$ and $101$.

length $4$: the words $1000$, $1001$ and $1011$.

length $5$: the words $10000$, $10001$, $10010$, $10011$, $10110$ and $10111$.

length $6$: the words $100000$, $100001$, $100010$, $100011$, $100110$, $100111$, $101100$, $101110$ and $101111$.

length $1$: the words $0$ and $1$. (For comparison: The Lyndon words are $0$ and $1$.)

length $2$: the word $10$. (For comparison: The Lyndon words are $01$.)

length $3$: the words $100$ and $101$. (For comparison: The Lyndon words are $001$ and $011$.)

length $4$: the words $1000$, $1001$ and $1011$. (For comparison: The Lyndon words are $0001$, $0011$ and $0111$.)

length $5$: the words $10000$, $10001$, $10010$, $10011$, $10110$ and $10111$. (For comparison: The Lyndon words are $00001$, $00011$, $00101$, $00111$, $01011$ and $01111$.)

length $6$: the words $100000$, $100001$, $100010$, $100011$, $100110$, $100111$, $101100$, $101110$ and $101111$. (For comparison: The Lyndon words are $000001$, $000011$, $000101$, $000111$, $001011$, $001101$, $001111$, $010111$ and $011111$.)