

A006245


Number of primitive sorting networks on n elements; also number of rhombic tilings of 2ngon.
(Formerly M1894)


19



1, 1, 2, 8, 62, 908, 24698, 1232944, 112018190, 18410581880, 5449192389984, 2894710651370536, 2752596959306389652, 4675651520558571537540, 14163808995580022218786390
(list;
graph;
refs;
listen;
history;
text;
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_{n1} (see Armstrong reference).
Also the number of oriented matroids of rank 3 on n elements (see FolkmanLawrence reference).  Matthew J. Samuel, Jan 19 2013
Also the number of mappings X:{{1..n} choose 3}>{+,} such that for any four indices a < b < c < d, the sequence X(a,b,c), X(a,b,d), X(a,c,d), X(b,c,d) changes its sign at most once (see FelsnerWeil and BalkoFulekKynčl reference).  Manfred Scheucher, Oct 20 2019


REFERENCES

D. E. Knuth, Axioms and hulls, Lect. Notes Comp. Sci., Vol. 606.
Shinichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 16.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Table of n, a(n) for n=1..15.
D. Armstrong, The sorting order on a Coxeter group, Journal of Combinatorial Theory 116 (2009), no. 8, 12851305.
M. Balko, R. Fulek, and J. Kynčl, Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n, Discrete & Computational Geometry, Volume 53, Issue 1, 2015, Pages 107143.
Yunhyung Cho, Jang Soo Kim, and Eunjeong Lee, Enumerate of GelfandCetlin type reduced words, arXiv:2009.06906 [math.CO], 2020. Mentions this sequence.
H. Denoncourt, D. C. Ernst, D. Story, On the number of commutation classes of the longest element in the symmetric group, arXiv:1602.08328 [math.HO], 2016.
Adrian Dumitrescu, Ritankar Mandal, New Lower Bounds for the Number of Pseudoline Arrangements, arXiv:1809.03619 [math.CO], 2018.
Stefan Felsner, On the number of arrangements of pseudolines, Proceedings of the twelfth annual symposium on Computational geometry. ACM, 1996. Also Discrete and Computational Geometry, 18 (1997),257267. Gives a(10).
S. Felsner and H. Weil, Sweeps, arrangements and signotopes, Discrete Applied Mathematics Volume 109, Issues 12, 2001, Pages 6794.
S. Felsner and P. Valtr, Coding and Counting Arrangements of Pseudolines, Discrete and Computational Geometry, 46(3) (2011), 405416.
J. Folkman and J. Lawrence, Oriented matroids, Journal of Combinatorial Theory, Series B 25 (1978), no. 2, 199236.
M. J. Hay, J. Schiff, N. J. Fisch, Available free energy under local phase space diffusion, arXiv preprint arXiv:1604.08573 [mathph], 2016, see Footnote 27.
J. Kawahara, T. Saitoh, R. Yoshinaka and S. Minato, Counting Primitive Sorting Networks by PiDDs, Hokkaido University, Division of Computer Science, TCS Technical Reports, TCSTRA1154, Oct. 2011.
D. E. Knuth, Axioms and Hulls, LNCS 606 (1992) p. 35. [From R. J. Mathar, Apr 02 2009]
S. Minato, Techniques of BDD/ZDD: Brief History and Recent Activity, IEICE Transactions on Information and Systems, Vol. E96D, No. 7, pp.14191429.
Matthew J. Samuel, Word posets, complexity, and Coxeter groups, arXiv:1101.4655 [math.CO], 2011.
M. J. Samuel, Word posets, with applications to Coxeter groups, arXiv preprint arXiv:1108.3638 [cs.DM], 2011.
B. E. Tenner, Tilingbased models of perimeter and area, arXiv:1811.00082 [math.CO], 2018.
M. Widom, N. Destainville, R. Mosseri and F. Bailly, Twodimensional random tilings of large codimension, Proceedings of the 7th International Conference on Quasicrystals (ICQ7, Stuttgart), arXiv:condmat/9912275 [condmat.statmech], 1999.
M. Widom, N. Destainville, R. Mosseri and F. Bailly, Twodimensional random tilings of large codimension, Materials Science and Engineering: A, Volumes 294296, 15 December 2000, Pages 409412.
Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno, Kunihiro Wasa, LadderLottery Realization, 30th Canadian Conference on Computational Geometry (CCCG 2018) Winnipeg.
K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara and K. Nakada, Efficient enumeration of all ladder lotteries and its application, Theoretical Computer Science, Vol. 411, pp. 17141722, 2010.
Index entries for sequences related to sorting


FORMULA

Felsner and Valtr show that 0.1887 <= log_2(a(n))/n^2 <= 0.6571 for sufficiently large n.  Jeremy Tan, Nov 20 2017


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, n1, ..., 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:
seq(classes([seq(n+1i, i = 1 .. n)]), n = 1 .. 9)
# Matthew J. Samuel, Jan 23 2011, Jan 26 2011


MATHEMATICA

classes[perm_List] := classes[perm] = classesRecurse[perm, 0, 1];
classesRecurse[perm_List, spot_, negs_] := Module[{swaps, i, Sums, c, doneany, prm = perm}, Sums = 0; doneany = 0; For[i = spot, i <= Length[prm]2, i++, If[prm[[i+1]] > prm[[i+2]], swaps = prm[[i+1]]; prm[[i+1]] = prm[[i+2]]; prm[[i+2]] = swaps; c = classes[prm]; Sums = Sums + negs*c + classesRecurse[prm, i+2, negs]; swaps = prm[[i+1]]; prm[[i+1]] = prm[[i+2]]; prm[[i+2]] = swaps; doneany = 1]]; If[spot == 0 && doneany == 0, Return[1], Return[Sums]]];
a[n_] := a[n] = classes[Range[n] // Reverse];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 9}] (* JeanFrançois Alcover, May 09 2017, translated from Maple *)


CROSSREFS

Cf. A006246.
Sequence in context: A192516 A159476 A230824 * A202751 A227160 A191604
Adjacent sequences: A006242 A006243 A006244 * A006246 A006247 A006248


KEYWORD

nonn,nice,more


AUTHOR

N. J. A. Sloane


EXTENSIONS

More terms from Sebastien Veigneau (sv(AT)univmlv.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, Jan 25 2011
Removed invalid comment concerning the denominators of the indicated polynomials; added a(12).  Matthew J. Samuel, Jan 30 2011
a(13) from Toshiki Saitoh, Oct 17 2011
a(14) and a(15) from Yuma Tanaka, Aug 20 2013


STATUS

approved



