Lyndon words¶
-
class
sage.combinat.lyndon_word.
LyndonWord
(data, check=True)¶ Bases:
sage.combinat.words.word.FiniteWord_list
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
is a word that is lexicographically less than all of its rotations. Equivalently, whenever
is split into two non-empty substrings,
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
(category=None)¶ Bases:
sage.combinat.words.words.Words_all
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)¶ Bases:
sage.combinat.combinat.CombinatorialClass
TESTS:
sage: LW21 = LyndonWords([2,1]); LW21 Lyndon words with evaluation [2, 1] sage: LW21 == loads(dumps(LW21)) 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)¶ Bases:
sage.combinat.words.words.FiniteWords_length_k_over_OrderedAlphabet
TESTS:
sage: LW23 = LyndonWords(2,3); LW23 Lyndon words from an alphabet of size 2 of length 3 sage: LW23== loads(dumps(LW23)) 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)¶ Bases:
sage.combinat.combinat.CombinatorialClass
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]]