login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180607 Number of commutation classes of reduced words for the longest element of a Weyl group of type D_n. 0
1, 1, 8, 182, 13198, 3031856, 2198620478, 5017961787334, 35964266585527318 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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

Table of n, a(n) for n=1..9.

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

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

CROSSREFS

Sequence in context: A261825 A203359 A294355 * A024286 A231795 A240319

Adjacent sequences:  A180604 A180605 A180606 * A180608 A180609 A180610

KEYWORD

nonn,hard,more

AUTHOR

Matthew J. Samuel, Jan 21 2011

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 18:45 EST 2019. Contains 320376 sequences. (Running on oeis4.)