|
%I #26 Jan 12 2019 20:23:04
%S 1,1,8,182,13198,3031856,2198620478,5017961787334,35964266585527318
%N Number of commutation classes of reduced words for the longest element of a Weyl group of type D_n.
%C 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!).
%H Matthew J. Samuel, <a href="http://arxiv.org/abs/1101.4655">Word posets, complexity, and Coxeter groups</a>, arXiv:1101.4655v1 [math.CO]
%p # classes: Wrapper for computing number of commutation classes;
%p # pass a permutation of type D as a list
%p # Returns number of commutation classes
%p # Longest element is of the form [-1, -2, ..., -n] if n is even,
%p # or [1, -2, -3, ..., -n] if n is odd
%p classes:=proc(perm) option remember:
%p classesRecurse(Array(perm), -1, 1):
%p end:
%p # classesRecurse: Recursive procedure for computing number of commutation classes
%p classesRecurse:=proc(perm, spot, negs) local swaps, i, sums, c, doneany:
%p sums:=0:
%p doneany:=0:
%p for i from spot to ArrayNumElems(perm)-2 do
%p if i=-1 and -perm[2]>perm[1] then
%p swaps:=perm[1]:
%p perm[1]:=-perm[2]:
%p perm[2]:=-swaps:
%p c:=classes(convert(perm, `list`)):
%p sums:=sums+negs*c+classesRecurse(perm, i+1, -negs):
%p swaps:=perm[1]:
%p perm[1]:=-perm[2]:
%p perm[2]:=-swaps:
%p doneany:=1:
%p elif i>-1 and perm[i+1]>perm[i+2] then
%p if not (spot=0 and i=1) then
%p swaps:=perm[i+1]:
%p perm[i+1]:=perm[i+2]:
%p perm[i+2]:=swaps:
%p c:=classes(convert(perm, `list`)):
%p sums:=sums+negs*c+classesRecurse(perm, i+2, -negs):
%p swaps:=perm[i+1]:
%p perm[i+1]:=perm[i+2]:
%p perm[i+2]:=swaps:
%p doneany:=1:
%p end:
%p end:
%p end:
%p if spot=-1 and doneany=0 then RETURN(1):
%p else RETURN(sums):
%p end:
%p end: # _Matthew J. Samuel_, Jan 24 2011, Jan 26 2011
%K nonn,hard,more
%O 1,3
%A _Matthew J. Samuel_, Jan 21 2011
%E a(9)=35964266585527318 computed with a Java program by _Matthew J. Samuel_, Jan 30 2011
| 