Lyndon words¶
-
sage.combinat.lyndon_word.
LyndonWord
(data, check=True)¶ Construction of a Lyndon word.
INPUT:
data
- listcheck
- 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 alphabetk
- 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() # random 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
(alphabet=None)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
The set of all Lyndon words.
-
class
sage.combinat.lyndon_word.
LyndonWords_evaluation
(e)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.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]
-
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)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
Lyndon words of fixed length \(n\) over the alphabet \({1, 2, ..., k}\).
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]
-
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)¶ Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
TESTS:
sage: SBLW = StandardBracketedLyndonWords(3, 2) sage: SBLW == loads(dumps(SBLW)) 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]]