# Lyndon words¶

class sage.combinat.lyndon_word.LyndonWord(data, check=True)

Construction of a Lyndon word.

INPUT:

• data - list
• check - bool (optional, default: True) if True, a verification that the input data represent 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


If check is False, then no verification is done:

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

sage.combinat.lyndon_word.LyndonWords(e=None, k=None)

Returns 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.

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


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,3); LW
Lyndon words from an alphabet of size 3 of length 3
sage: LW.first()
word: 112
sage: LW.last()
word: 233
sage: LW.random_element()
word: 112
sage: LW.cardinality()
8


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]

class sage.combinat.lyndon_word.LyndonWords_class(category=None, *keys, **opts)

TESTS:

sage: C = sage.combinat.combinat.CombinatorialClass()
sage: C.category()
Category of enumerated sets
sage: C.__class__
<class 'sage.combinat.combinat.CombinatorialClass_with_category'>
sage: isinstance(C, Parent)
True
sage: C = sage.combinat.combinat.CombinatorialClass(category = FiniteEnumeratedSets())
sage: C.category()
Category of finite enumerated sets

class sage.combinat.lyndon_word.LyndonWords_evaluation(e)

TESTS:

sage: LW21 = LyndonWords([2,1]); LW21
Lyndon words with evaluation [2, 1]
True

cardinality()

Returns the number of Lyndon words with the evaluation e.

EXAMPLES:

sage: LyndonWords([]).cardinality()
0
sage: LyndonWords([2,2]).cardinality()
1
sage: LyndonWords([2,3,2]).cardinality()
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] )
True

class sage.combinat.lyndon_word.LyndonWords_nk(n, k)

TESTS:

sage: LW23 = LyndonWords(2,3); LW23
Lyndon words from an alphabet of size 2 of length 3
True

cardinality()

TESTS:

sage: [ LyndonWords(3,i).cardinality() for i in range(1, 11) ]
[3, 3, 8, 18, 48, 116, 312, 810, 2184, 5880]

sage.combinat.lyndon_word.StandardBracketedLyndonWords(n, k)

Returns 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()
[1, [1, 2]]

class sage.combinat.lyndon_word.StandardBracketedLyndonWords_nk(n, k)

TESTS:

sage: SBLW = StandardBracketedLyndonWords(3, 2)
True

cardinality()

EXAMPLES:

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

sage.combinat.lyndon_word.standard_bracketing(lw)

Returns the standard bracketing of a Lyndon word lw.

EXAMPLES:

sage: import sage.combinat.lyndon_word as lyndon_word
sage: map( lyndon_word.standard_bracketing, 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]]


Latin Squares

Necklaces