Return to Answer

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function

WeightedIntegerVectors(d,[d1,..,dk])

which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,

LyndonWords(L):

will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. There is just a small issue: the LyndonWords function seems to have trouble with lists beginning by 0, so the code below does'nt really works.. I just send a bug report. Example:

for i in range(1,6):
print "degree "+str(i)
L=WeightedIntegerVectors(i,[1,2])
for l in L:
     for w in LyndonWords(list(l)):
         print sage.combinat.lyndon_word.standard_bracketing(w)

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function

WeightedIntegerVectors(d,[d1,..,dk])

which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,

LyndonWords(L):

will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. Warning: there is just a small issue: the LyndonWords function seems to have trouble with lists beginning by 0, so the code below use a modified function, see the end of this post...

Example:

for i in range(1,6):
print "degree "+str(i)
L=WeightedIntegerVectors(i,[1,2])
for l in L:
     for w in MyLyndon(list(l)):
         print sage.combinat.lyndon_word.standard_bracketing(w)

gives

degree 1
1
degree 2
2
degree 3
[1, 2]
degree 4
[1, [1, 2]]
degree 5
[[1, 2], 2]
[1, [1, [1, 2]]]

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.

If I'm not wrong, a Lyndon word o composition $(0,\dots,0,k_{j+1},\dots,k_n)$ with $j$ 0's at the beginning is the same as a Lyndon word of composition $(k_{j+1},\dots,k_n)$ with letters shifted by $j$ (since it has to be a Lyndon basis of the sub-Lie algebra generated by $x_{j+1},\dots,x_n$. So hopefully the following code will do the trick:

def myLyndon(e):
if e == []:
    return
k=0
while (e[k]==0):
    k=k+1
for z in sage.combinat.necklace._sfc(e[k:], equality=True):
    yield LyndonWord([i+k+1 for i in z], check=False)

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function

WeightedIntegerVectors(d,[d1,..,dk])

which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,

LyndonWords(L):

will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. There is just a small issue: the LyndonWords function seems to have trouble with lists containing 0's, so I excluded them, which of course excluded the generators themselves of the result (and only them, since other elements contains at least two distinct generators).

Example:

for i in range(1,6):
print "degree "+str(i)
L=WeightedIntegerVectors(i,[1,2])
for l in L:
    if not (0 in l):
        for w in LyndonWords(list(l)):
            print sage.combinat.lyndon_word.standard_bracketing(w)

returns:

degree 1
degree 2
degree 3
[1, 2]
degree 4
[1, [1, 2]]
degree 5
[[1, 2], 2]
[1, [1, [1, 2]]]

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function

WeightedIntegerVectors(d,[d1,..,dk])

which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,

LyndonWords(L):

will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. There is just a small issue: the LyndonWords function seems to have trouble with lists beginning by 0, so the code below does'nt really works.. I just send a bug report. Example:

for i in range(1,6):
print "degree "+str(i)
L=WeightedIntegerVectors(i,[1,2])
for l in L:
     for w in LyndonWords(list(l)):
         print sage.combinat.lyndon_word.standard_bracketing(w)

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function

WeightedIntegerVectors(d,[d1,..,dk])

which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,

LyndonWords(L):

will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. There is just a small issue: the LyndonWords function seems to have trouble with lists containing 0's, so I excluded them, which of course excluded the generators themselves of the result.

Example:

for i in range(1,6):
print "degree "+str(i)
L=WeightedIntegerVectors(i,[1,2])
for l in L:
    if not (0 in l):
        for w in LyndonWords(list(l)):
            print sage.combinat.lyndon_word.standard_bracketing(w)

returns:

degree 1
degree 2
degree 3
[1, 2]
degree 4
[1, [1, 2]]
degree 5
[[1, 2], 2]
[1, [1, [1, 2]]]

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.

These are easily obtained with SAGE:

for i in range(1,6):
 for w in StandardBracketedLyndonWords(2, i):
     print w

Edit: And for the graded case, since the function which generates Lyndon words knows what a composition is, you can use the function

WeightedIntegerVectors(d,[d1,..,dk])

which find all positive solutions of $$\sum \lambda_i d_i=d$$ for a given $d$. Then for any given solution $L=[\lambda_1,\dots,\lambda_n]$ in the form of a Python list,

LyndonWords(L):

will return all the Lyndon words on $n$ letters containing exactly $\lambda_i$ times the $i$th letter. You'll get this way all Lyndon words of degree $d$. There is just a small issue: the LyndonWords function seems to have trouble with lists containing 0's, so I excluded them, which of course excluded the generators themselves of the result (and only them, since other elements contains at least two distinct generators).

Example:

for i in range(1,6):
print "degree "+str(i)
L=WeightedIntegerVectors(i,[1,2])
for l in L:
    if not (0 in l):
        for w in LyndonWords(list(l)):
            print sage.combinat.lyndon_word.standard_bracketing(w)

returns:

degree 1
degree 2
degree 3
[1, 2]
degree 4
[1, [1, 2]]
degree 5
[[1, 2], 2]
[1, [1, [1, 2]]]

Since Omar pointed this out, let me recall that standard bracketing of Lyndon words provides a Hall basis, maybe not "the" Hall basis you have in mind.