|
%I #32 Sep 04 2019 09:29:16
%S 1,2,14,330,25396,6272842,4925166862,12221171869734,95482373388042562
%N Number of commutation classes of reduced words for the longest element of a Weyl group of type B_n.
%H <a href="/A180605/b180605.txt">Table of n, a(n) for n = 1..9</a>
%H Matthew J. Samuel, <a href="http://arxiv.org/abs/1101.4655">Word posets, complexity, and Coxeter groups</a>, arXiv:1101.4655 [math.CO]
%e For n=2 the a(2)=2 commutation classes of words are 0101 and 1010.
%e 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.
%p #classes: Wrapper for computing number of commutation classes; pass a permutation of type B as a list
%p #Returns number of commutation classes
%p #Longest element is of the form [-1, -2, ..., -n]
%p classes:=proc(perm) option remember:
%p RETURN(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[1]<0 then
%p perm[1]:=-perm[1]:
%p c:=classes(convert(perm,`list`)):
%p sums:=sums+negs*c+classesRecurse(perm,i+2,-negs):
%p perm[1]:=-perm[1]:
%p doneany:=1:
%p elif i>-1 and perm[i+1]>perm[i+2] 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 if spot=-1 and doneany=0 then RETURN(1):
%p else RETURN(sums):
%p end:
%p end:
%K nonn,hard,more
%O 1,2
%A _Matthew J. Samuel_, Jan 21 2011
%E a(9) computed with a Java program by _Matthew J. Samuel_, Jan 30 2011
| 