|
| |
|
|
A006245
|
|
Number of primitive sorting networks on n elements; also number of rhombic tilings of 2n-gon.
(Formerly M1894)
|
|
14
| |
|
|
1, 1, 2, 8, 62, 908, 24698, 1232944, 112018190, 18410581880, 5449192389984, 2894710651370536, 2752596959306389652
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Also the number of commutation classes of reduced words for the longest element of a Weyl group of type A_{n-1} (see Armstrong reference).
|
|
|
REFERENCES
| D. Armstrong, The sorting order on a Coxeter group, Journal of Combinatorial Theory 116 (2009), no. 8, 1285-1305.
J. Kawahara, T. Saitoh, R. Yoshinaka and S. Minato: "Counting Primitive Sorting Networks by PiDDs," Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-11-54, Oct. 2011.
D. E. Knuth, Axioms and hulls, Lect. Notes Comp. Sci., Vol. 606.
M. J. Samuel, Word posets, with applications to Coxeter groups, Arxiv preprint arXiv:1108.3638, 2011
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara and K. Nakada, "Efficient Enumeration of All Pseudoline Arrangements," Proc. 25th European Workshop on Computer Geometry ((EuroCG09)), pp. 143-146, 200.
|
|
|
LINKS
| J. Kawahara, T. Saitoh, R. Yoshinaka and S. Minato, Counting Primitive Sorting Networks by PiDDs
D. E. Knuth, Axioms and Hulls, LNCS 606 (1992) p35. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Apr 02 2009]
Matthew J. Samuel, Word posets, complexity, and Coxeter groups, arXiv:1101.4655 [math.CO]
M. Widom, N. Destainville, R. Mosseri and F. Bailly, Two-dimensional random tilings of large codimension
Index entries for sequences related to sorting
|
|
|
MAPLE
| # classes: Wrapper for computing number of commutation classes;
# pass a permutation as a list
# Returns number of commutation classes of reduced words
# Longest element is of the form [n, n-1, ..., 1] (see Comments)
classes:=proc(perm) option remember:
RETURN(classesRecurse(Array(perm), 0, 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 perm[i+1]>perm[i+2] 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:
if spot=0 and doneany=0 then RETURN(1):
else RETURN(sums):
end:
end: ## From Matthew J. Samuel, Jan 23 2011, Jan 26 2011
|
|
|
CROSSREFS
| Cf. A006246.
Sequence in context: A161566 A192516 A159476 * A202751 A191604 A009271
Adjacent sequences: A006242 A006243 A006244 * A006246 A006247 A006248
|
|
|
KEYWORD
| nonn,nice,more
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Sebastien VEIGNEAU (sv(AT)univ-mlv.fr) Jan 15 1997.
a(10) confirmed by Katsuhisa Yamanaka(<yamanaka(AT)hol.is.uec.ac.jp), May 06 2009. This value was also confirmed by Takashi Horiyama of Saitama Univ.
a(11) from Katsuhisa Yamanaka(<yamanaka(AT)hol.is.uec.ac.jp), May 06 2009.
Reference with formula that the Maple program implements added and a(11) verified by Matthew J. Samuel (msamuel(AT)math.rutgers.edu), Jan 25 2011
Removed invalid comment concerning the denominators of the indicated amazing polynomials; added a(12). - Matthew J. Samuel (msamuel(AT)math.rutgers.edu), Jan 30 2011
a(13) from Toshiki Saitoh (t-saitoh(AT)erato.ist.hokudai.ac.jp), Oct 17 2011.
|
| |
|
|
