This site is supported by donations to The OEIS Foundation.

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

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