A180607 Number of commutation classes of reduced words for the longest element of a Weyl group of type D_n.

1, 1, 8, 182, 13198, 3031856, 2198620478, 5017961787334, 35964266585527318

Offset: 1

Author

Matthew J. Samuel, Jan 21 2011

Keywords

• nonn
• hard
• more

Comments

An implementation of the procedures below in Java with the additional feature of storing old values of classesRecurse(perm,-1,1) computed a(8)=5017961787334 in 63 seconds. The program runs in O((n^2)*(4^n)*n!).

Links

• Matthew J. Samuel, Word posets, complexity, and Coxeter groups, arXiv:1101.4655v1 [math.CO]

Programs

Maple

# classes: Wrapper for computing number of commutation classes;
#   pass a permutation of type D as a list
# Returns number of commutation classes
# Longest element is of the form [-1, -2, ..., -n] if n is even,
#   or [1, -2, -3, ..., -n] if n is odd
classes:=proc(perm) option remember:
    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[2]>perm[1] then
            swaps:=perm[1]:
            perm[1]:=-perm[2]:
            perm[2]:=-swaps:
            c:=classes(convert(perm, `list`)):
            sums:=sums+negs*c+classesRecurse(perm, i+1, -negs):
            swaps:=perm[1]:
            perm[1]:=-perm[2]:
            perm[2]:=-swaps:
            doneany:=1:
        elif i>-1 and perm[i+1]>perm[i+2] then
            if not (spot=0 and i=1) 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:
    end:
    if spot=-1 and doneany=0 then RETURN(1):
    else RETURN(sums):
    end:
end: # Matthew J. Samuel, Jan 24 2011, Jan 26 2011

Extensions

a(9)=35964266585527318 computed with a Java program by Matthew J. Samuel, Jan 30 2011