OFFSET
1,2
LINKS
Matthew J. Samuel, Word posets, complexity, and Coxeter groups, arXiv:1101.4655 [math.CO]
EXAMPLE
For n=2 the a(2)=2 commutation classes of words are 0101 and 1010.
For n=3 the a(3)=14 commutation classes of words are those of 210121010, 121012010, 212012010, 120101210, 101210120, 120120120, 210120101, 201012101, 012101201, 201201201, 012010121, 101201012, 010121012, 012012012.
MAPLE
#classes: Wrapper for computing number of commutation classes; pass a permutation of type B as a list
#Returns number of commutation classes
#Longest element is of the form [-1, -2, ..., -n]
classes:=proc(perm) option remember:
RETURN(classesRecurse(Array(perm), -1, 1)):
end:
#classesRecurse: Recursive procedure for computing number of commutation classes
classesRecurse:=proc(perm, spot, negs) local swaps, i, sums, c, doneany:
sums:=0:
doneany:=0:
for i from spot to ArrayNumElems(perm)-2 do
if i=-1 and perm[1]<0 then
perm[1]:=-perm[1]:
c:=classes(convert(perm, `list`)):
sums:=sums+negs*c+classesRecurse(perm, i+2, -negs):
perm[1]:=-perm[1]:
doneany:=1:
elif i>-1 and perm[i+1]>perm[i+2] then
swaps:=perm[i+1]:
perm[i+1]:=perm[i+2]:
perm[i+2]:=swaps:
c:=classes(convert(perm, `list`)):
sums:=sums+negs*c+classesRecurse(perm, i+2, -negs):
swaps:=perm[i+1]:
perm[i+1]:=perm[i+2]:
perm[i+2]:=swaps:
doneany:=1:
end:
end:
if spot=-1 and doneany=0 then RETURN(1):
else RETURN(sums):
end:
end:
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Matthew J. Samuel, Jan 21 2011
EXTENSIONS
a(9) computed with a Java program by Matthew J. Samuel, Jan 30 2011
STATUS
approved