Lyndon words

sage.combinat.words.lyndon_word.LyndonWord(data, check=True)[source]

Construction of a Lyndon word.

INPUT:

  • data – list

  • check – boolean (default: True); if True, check that the input data represents a Lyndon word

OUTPUT: a Lyndon word

EXAMPLES:

sage: LyndonWord([1,2,2])
word: 122
sage: LyndonWord([1,2,3])
word: 123
sage: LyndonWord([2,1,2,3])
Traceback (most recent call last):
...
ValueError: not a Lyndon word

>>> from sage.all import *
>>> LyndonWord([Integer(1),Integer(2),Integer(2)])
word: 122
>>> LyndonWord([Integer(1),Integer(2),Integer(3)])
word: 123
>>> LyndonWord([Integer(2),Integer(1),Integer(2),Integer(3)])
Traceback (most recent call last):
...
ValueError: not a Lyndon word

If check is False, then no verification is done:

sage: LyndonWord([2,1,2,3], check=False)
word: 2123

>>> from sage.all import *
>>> LyndonWord([Integer(2),Integer(1),Integer(2),Integer(3)], check=False)
word: 2123
sage.combinat.words.lyndon_word.LyndonWords(e=None, k=None)[source]

Return the combinatorial class of Lyndon words.

A Lyndon word \(w\) is a word that is lexicographically less than all of its rotations. Equivalently, whenever \(w\) is split into two non-empty substrings, \(w\) is lexicographically less than the right substring.

See Wikipedia article Lyndon_word

INPUT:

  • no input at all

or

  • e – integer; size of alphabet

  • k – integer; length of the words

or

  • e – a composition

OUTPUT: a combinatorial class of Lyndon words

EXAMPLES:

sage: LyndonWords()
Lyndon words

>>> from sage.all import *
>>> LyndonWords()
Lyndon words

If e is an integer, then e specifies the length of the alphabet; k must also be specified in this case:

sage: LW = LyndonWords(3, 4); LW
Lyndon words from an alphabet of size 3 of length 4
sage: LW.first()
word: 1112
sage: LW.last()
word: 2333
sage: LW.random_element()  # random                                             # needs sage.libs.pari
word: 1232
sage: LW.cardinality()                                                          # needs sage.libs.pari
18

>>> from sage.all import *
>>> LW = LyndonWords(Integer(3), Integer(4)); LW
Lyndon words from an alphabet of size 3 of length 4
>>> LW.first()
word: 1112
>>> LW.last()
word: 2333
>>> LW.random_element()  # random                                             # needs sage.libs.pari
word: 1232
>>> LW.cardinality()                                                          # needs sage.libs.pari
18

If e is a (weak) composition, then it returns the class of Lyndon words that have evaluation e:

sage: LyndonWords([2, 0, 1]).list()
[word: 113]
sage: LyndonWords([2, 0, 1, 0, 1]).list()
[word: 1135, word: 1153, word: 1315]
sage: LyndonWords([2, 1, 1]).list()
[word: 1123, word: 1132, word: 1213]

>>> from sage.all import *
>>> LyndonWords([Integer(2), Integer(0), Integer(1)]).list()
[word: 113]
>>> LyndonWords([Integer(2), Integer(0), Integer(1), Integer(0), Integer(1)]).list()
[word: 1135, word: 1153, word: 1315]
>>> LyndonWords([Integer(2), Integer(1), Integer(1)]).list()
[word: 1123, word: 1132, word: 1213]
class sage.combinat.words.lyndon_word.LyndonWords_class(alphabet=None)[source]

Bases: UniqueRepresentation, Parent

The set of all Lyndon words.

class sage.combinat.words.lyndon_word.LyndonWords_evaluation(e)[source]

Bases: UniqueRepresentation, Parent

The set of Lyndon words on a fixed multiset of letters.

EXAMPLES:

sage: L = LyndonWords([1,2,1])
sage: L
Lyndon words with evaluation [1, 2, 1]
sage: L.list()
[word: 1223, word: 1232, word: 1322]

>>> from sage.all import *
>>> L = LyndonWords([Integer(1),Integer(2),Integer(1)])
>>> L
Lyndon words with evaluation [1, 2, 1]
>>> L.list()
[word: 1223, word: 1232, word: 1322]
cardinality()[source]

Return the number of Lyndon words with the evaluation e.

EXAMPLES:

sage: LyndonWords([]).cardinality()
0
sage: LyndonWords([2,2]).cardinality()                                      # needs sage.libs.pari
1
sage: LyndonWords([2,3,2]).cardinality()                                    # needs sage.libs.pari
30

>>> from sage.all import *
>>> LyndonWords([]).cardinality()
0
>>> LyndonWords([Integer(2),Integer(2)]).cardinality()                                      # needs sage.libs.pari
1
>>> LyndonWords([Integer(2),Integer(3),Integer(2)]).cardinality()                                    # needs sage.libs.pari
30

Check to make sure that the count matches up with the number of Lyndon words generated:

sage: comps = [[],[2,2],[3,2,7],[4,2]] + Compositions(4).list()
sage: lws = [LyndonWords(comp) for comp in comps]
sage: all(lw.cardinality() == len(lw.list()) for lw in lws)                 # needs sage.libs.pari
True

>>> from sage.all import *
>>> comps = [[],[Integer(2),Integer(2)],[Integer(3),Integer(2),Integer(7)],[Integer(4),Integer(2)]] + Compositions(Integer(4)).list()
>>> lws = [LyndonWords(comp) for comp in comps]
>>> all(lw.cardinality() == len(lw.list()) for lw in lws)                 # needs sage.libs.pari
True
class sage.combinat.words.lyndon_word.LyndonWords_nk(n, k)[source]

Bases: UniqueRepresentation, Parent

Lyndon words of fixed length \(k\) over the alphabet \(\{1, 2, \ldots, n\}\).

INPUT:

  • n – the size of the alphabet

  • k – the length of the words

EXAMPLES:

sage: L = LyndonWords(3, 4)
sage: L.list()
[word: 1112,
 word: 1113,
 word: 1122,
 word: 1123,
 ...
 word: 1333,
 word: 2223,
 word: 2233,
 word: 2333]

>>> from sage.all import *
>>> L = LyndonWords(Integer(3), Integer(4))
>>> L.list()
[word: 1112,
 word: 1113,
 word: 1122,
 word: 1123,
 ...
 word: 1333,
 word: 2223,
 word: 2233,
 word: 2333]
cardinality()[source]
sage.combinat.words.lyndon_word.StandardBracketedLyndonWords(n, k)[source]

Return the combinatorial class of standard bracketed Lyndon words from [1, …, n] of length k.

These are in one to one correspondence with the Lyndon words and form a basis for the subspace of degree k of the free Lie algebra of rank n.

EXAMPLES:

sage: SBLW33 = StandardBracketedLyndonWords(3,3); SBLW33
Standard bracketed Lyndon words from an alphabet of size 3 of length 3
sage: SBLW33.first()
[1, [1, 2]]
sage: SBLW33.last()
[[2, 3], 3]
sage: SBLW33.cardinality()
8
sage: SBLW33.random_element() in SBLW33
True

>>> from sage.all import *
>>> SBLW33 = StandardBracketedLyndonWords(Integer(3),Integer(3)); SBLW33
Standard bracketed Lyndon words from an alphabet of size 3 of length 3
>>> SBLW33.first()
[1, [1, 2]]
>>> SBLW33.last()
[[2, 3], 3]
>>> SBLW33.cardinality()
8
>>> SBLW33.random_element() in SBLW33
True
class sage.combinat.words.lyndon_word.StandardBracketedLyndonWords_nk(n, k)[source]

Bases: UniqueRepresentation, Parent

cardinality()[source]

EXAMPLES:

sage: StandardBracketedLyndonWords(3, 3).cardinality()
8
sage: StandardBracketedLyndonWords(3, 4).cardinality()
18

>>> from sage.all import *
>>> StandardBracketedLyndonWords(Integer(3), Integer(3)).cardinality()
8
>>> StandardBracketedLyndonWords(Integer(3), Integer(4)).cardinality()
18
sage.combinat.words.lyndon_word.standard_bracketing(lw)[source]

Return the standard bracketing of a Lyndon word lw.

EXAMPLES:

sage: import sage.combinat.words.lyndon_word as lyndon_word
sage: [lyndon_word.standard_bracketing(u) for u in LyndonWords(3,3)]
[[1, [1, 2]],
 [1, [1, 3]],
 [[1, 2], 2],
 [1, [2, 3]],
 [[1, 3], 2],
 [[1, 3], 3],
 [2, [2, 3]],
 [[2, 3], 3]]

>>> from sage.all import *
>>> import sage.combinat.words.lyndon_word as lyndon_word
>>> [lyndon_word.standard_bracketing(u) for u in LyndonWords(Integer(3),Integer(3))]
[[1, [1, 2]],
 [1, [1, 3]],
 [[1, 2], 2],
 [1, [2, 3]],
 [[1, 3], 2],
 [[1, 3], 3],
 [2, [2, 3]],
 [[2, 3], 3]]
sage.combinat.words.lyndon_word.standard_unbracketing(sblw)[source]

Return flattened sblw if it is a standard bracketing of a Lyndon word, otherwise raise an error.

EXAMPLES:

sage: from sage.combinat.words.lyndon_word import standard_unbracketing
sage: standard_unbracketing([1, [2, 3]])
word: 123
sage: standard_unbracketing([[1, 2], 3])
Traceback (most recent call last):
...
ValueError: not a standard bracketing of a Lyndon word

>>> from sage.all import *
>>> from sage.combinat.words.lyndon_word import standard_unbracketing
>>> standard_unbracketing([Integer(1), [Integer(2), Integer(3)]])
word: 123
>>> standard_unbracketing([[Integer(1), Integer(2)], Integer(3)])
Traceback (most recent call last):
...
ValueError: not a standard bracketing of a Lyndon word