|
|
A246865
|
|
Total number of reduced decompositions for all permutations in S_n.
|
|
2
|
|
|
1, 1, 2, 7, 66, 3061, 1095266, 3906746485, 165835140118904, 96867653699340061187, 883158060528372369857672080, 140546577721904223563711600192372503
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
A decomposition of a permutation is a product of adjacent transpositions. A reduced decomposition is one of minimal length which is also the number of inversions of the permutation and there may be more than one reduced decomposition. The largest number (multiplicity) of reduced decompositions of a permutation in S_n is A005118(n) for the permutation which reverses the order of all elements and all of its reduced decompositions have length n(n-1)/2 which is the maximum number of inversions. - Michael Somos, Sep 07 2014
|
|
REFERENCES
|
Bridget Eileen Tenner, Enumerating in Coxeter Groups (Survey), Advances in Mathematical Sciences, pp 75-82, Springer 2020.
|
|
LINKS
|
|
|
EXAMPLE
|
a(4) = 66 is summarized in a table of multiplicity versus length:
length = 0 1 2 3 4 5 6
multiplicity +---------------------+
1 | 1 3 4 2 . . . | = 10 1*10 = 10
2 | . . 1 4 1 . . | = 6 2*6 = 12
3 | . . . . 4 . . | = 4 3*4 = 12
5 | . . . . . 2 . | = 2 5*2 = 10
6 | . . . . . 1 . | = 1 6*1 = 6
16 | . . . . . . 1 | = 1 16*1 = 16
+---------------------+ -- --
1 3 5 6 5 3 1 = 24 a(4) = 66.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|