18.15 Lyndon words

Module: sage.combinat.lyndon_word

Lyndon words

Module-level Functions

LyndonWords( e, [k=None])

Returns the combinatorial class of 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()
[1, 1, 2]
sage: LW.last()
[2, 3, 3]
sage: LW.random_element()
[1, 1, 2]
sage: LW.count()
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()
[[1, 1, 3]]
sage: LyndonWords([2, 0, 1, 0, 1]).list()
[[1, 1, 3, 5], [1, 1, 5, 3], [1, 3, 1, 5]]
sage: LyndonWords([2, 1, 1]).list()
[[1, 1, 2, 3], [1, 1, 3, 2], [1, 2, 1, 3]]

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.

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.count()
8
sage: SBLW33.random_element()
[1, [1, 2]]

standard_bracketing( lw)

Returns the standard bracketing of a Lyndon word lw.

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]]

Class: LyndonWords_evaluation

class LyndonWords_evaluation
LyndonWords_evaluation( self, e)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

Returns the number of Lyndon words with the evaluation e.

sage: LyndonWords([]).count()
0
sage: LyndonWords([2,2]).count()
1
sage: LyndonWords([2,3,2]).count()
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.count() == len(lw.list()) for lw in lws] )
True

iterator( self)

An iterator for the Lyndon words with evaluation e.

sage: LyndonWords([1]).list()    #indirect doctest
[[1]]
sage: LyndonWords([2]).list()    #indirect doctest
[]
sage: LyndonWords([3]).list()    #indirect doctest
[]
sage: LyndonWords([3,1]).list()  #indirect doctest
[[1, 1, 1, 2]]
sage: LyndonWords([2,2]).list()  #indirect doctest
[[1, 1, 2, 2]]
sage: LyndonWords([1,3]).list()  #indirect doctest
[[1, 2, 2, 2]]
sage: LyndonWords([3,3]).list()  #indirect doctest
[[1, 1, 1, 2, 2, 2], [1, 1, 2, 1, 2, 2], [1, 1, 2, 2, 1, 2]]
sage: LyndonWords([4,3]).list()  #indirect doctest
[[1, 1, 1, 1, 2, 2, 2],
 [1, 1, 1, 2, 1, 2, 2],
 [1, 1, 1, 2, 2, 1, 2],
 [1, 1, 2, 1, 1, 2, 2],
 [1, 1, 2, 1, 2, 1, 2]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: [1,2,1,2] in LyndonWords([2,2])
False
sage: [1,1,2,2] in LyndonWords([2,2])
True
sage: all([ lw in LyndonWords([2,1,3,1]) for lw in LyndonWords([2,1,3,1])])
True

__repr__( self)

TESTS:

sage: repr(LyndonWords([2,1,1]))
'Lyndon words with evaluation [2, 1, 1]'

Class: LyndonWords_nk

class LyndonWords_nk
LyndonWords_nk( self, n, k)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

TESTS:

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

iterator( self)

TESTS:

sage: LyndonWords(3,3).list() # indirect doctest
[[1, 1, 2],
 [1, 1, 3],
 [1, 2, 2],
 [1, 2, 3],
 [1, 3, 2],
 [1, 3, 3],
 [2, 2, 3],
 [2, 3, 3]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

sage: LW33 = LyndonWords(3,3)
sage: all([lw in LW33 for lw in LW33])
True

__repr__( self)

TESTS:

sage: repr(LyndonWords(2, 3))
'Lyndon words from an alphabet of size 2 of length 3'

Class: StandardBracketedLyndonWords_nk

class StandardBracketedLyndonWords_nk
StandardBracketedLyndonWords_nk( self, n, k)

TESTS:

sage: SBLW = StandardBracketedLyndonWords(3, 2)
sage: SBLW == loads(dumps(SBLW))
True

Functions: count,$ \,$ iterator

count( self)

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

iterator( self)

sage: StandardBracketedLyndonWords(3, 3).list()
[[1, [1, 2]],
 [1, [1, 3]],
 [[1, 2], 2],
 [1, [2, 3]],
 [[1, 3], 2],
 [[1, 3], 3],
 [2, [2, 3]],
 [[2, 3], 3]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(StandardBracketedLyndonWords(3, 3))
'Standard bracketed Lyndon words from an alphabet of size 3 of length 3'

See About this document... for information on suggesting changes.