login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006245 Number of primitive sorting networks on n elements; also number of rhombic tilings of a 2n-gon.
(Formerly M1894)
23

%I M1894 #209 Nov 15 2023 06:00:23

%S 1,1,2,8,62,908,24698,1232944,112018190,18410581880,5449192389984,

%T 2894710651370536,2752596959306389652,4675651520558571537540,

%U 14163808995580022218786390,76413073725772593230461936736

%N Number of primitive sorting networks on n elements; also number of rhombic tilings of a 2n-gon.

%C 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).

%C Also the number of signotopes of rank 3, i.e., 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 Felsner-Weil and Balko-Fulek-Kynčl reference). - _Manfred Scheucher_, Oct 20 2019

%C There is a relation to non-degenerate oriented matroids of rank 3 on n elements (see Folkman-Lawrence reference). - _Manfred Scheucher_, Feb 09 2022, based on comment by _Matthew J. Samuel_, Jan 19 2013

%C Also the number of tilings of the 2-dimensional zonotope constructed from D vectors. The zonotope Z(D,d) is the projection of the D-dimensional hypercube onto the d-dimensional space and the tiles are the projections of the d-dimensional faces of the hypercube. Here d=2 and D varies.

%C Also the number of simple arrangements of n pseudolines in the Euclidean plane. - _Manfred Scheucher_, Jun 22 2023

%D Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H D. Armstrong, <a href="https://doi.org/10.1016/j.jcta.2009.03.009">The sorting order on a Coxeter group</a>, Journal of Combinatorial Theory 116 (2009), no. 8, 1285-1305.

%H M. Balko, R. Fulek and J. Kynčl, <a href="http://doi.org/10.1007/s00454-014-9644-z">Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n</a>, Discrete & Computational Geometry, Volume 53, Issue 1, 2015, Pages 107-143.

%H Helena Bergold, Stefan Felsner, and Manfred Scheucher, <a href="http://page.math.tu-berlin.de/~scheuch/publ/bfs-ehds-eurocg22.pdf">Extendability of higher dimensional signotopes</a>, Proc. 38th Eur. Wksp. Comp. Geom. (EuroCG), 2022. See also <a href="https://arxiv.org/abs/2303.04079">arXiv:2303.04079</a> [math.CO], 2023.

%H Yunhyung Cho, Jang Soo Kim and Eunjeong Lee, <a href="https://arxiv.org/abs/2009.06906">Enumerate of Gelfand-Cetlin type reduced words</a>, arXiv:2009.06906 [math.CO], 2020. Mentions this sequence.

%H H. Denoncourt, D. C. Ernst and D. Story, <a href="https://arxiv.org/abs/1602.08328">On the number of commutation classes of the longest element in the symmetric group</a>, arXiv:1602.08328 [math.HO], 2016.

%H Adrian Dumitrescu and Ritankar Mandal, <a href="https://arxiv.org/abs/1809.03619">New Lower Bounds for the Number of Pseudoline Arrangements</a>, arXiv:1809.03619 [math.CO], 2018.

%H Stefan Felsner, <a href="http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf">On the number of arrangements of pseudolines</a>, Proceedings of the twelfth annual symposium on Computational geometry. ACM, 1996. Also Discrete and Computational Geometry, 18 (1997),257-267. Gives a(10).

%H Stefan Felsner and Jacob E. Goodman, <a href="https://www.csun.edu/~ctoth/Handbook/chap5.pdf">Pseudoline Arrangements</a>, Chapter 5 of Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [Specific reference for this sequence] - _N. J. A. Sloane_, Nov 14 2023

%H S. Felsner and P. Valtr, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.224.8115">Coding and Counting Arrangements of Pseudolines</a>, Discrete and Computational Geometry, 46(3) (2011), 405-416.

%H S. Felsner and H. Weil, <a href="http://doi.org/10.1016/S0166-218X(00)00232-8">Sweeps, arrangements and signotopes</a>, Discrete Applied Mathematics Volume 109, Issues 1-2, 2001, Pages 67-94.

%H J. Folkman and J. Lawrence, <a href="https://doi.org/10.1016/0095-8956(78)90039-4">Oriented matroids</a>, Journal of Combinatorial Theory, Series B 25 (1978), no. 2, 199-236.

%H Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, <a href="https://www.csun.edu/~ctoth/Handbook/HDCG3.html">Handbook of Discrete and Computational Geometry</a>, CRC Press, 2017, see Table 5.6.1. [General reference for 2017 edition of the Handbook] - _N. J. A. Sloane_, Nov 14 2023

%H M. J. Hay, J. Schiff and N. J. Fisch, <a href="http://arxiv.org/abs/1604.08573">Available free energy under local phase space diffusion</a>, arXiv preprint arXiv:1604.08573 [math-ph], 2016, see Footnote 27.

%H J. Kawahara, T. Saitoh, R. Yoshinaka and S. Minato, <a href="http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/TR/ABSTRACTS/abstr_tcstr11_54.html">Counting Primitive Sorting Networks by PiDDs</a>, Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-11-54, Oct. 2011.

%H D. E. Knuth, <a href="http://dx.doi.org/10.1007/3-540-55611-7">Axioms and Hulls</a>, Lect. Notes Comp. Sci., Vol. 606 (1992) p. 35. [From _R. J. Mathar_, Apr 02 2009]

%H S. Minato, <a href="http://doi.org/10.1587/transinf.E96.D.1419">Techniques of BDD/ZDD: Brief History and Recent Activity</a>, IEICE Transactions on Information and Systems, Vol. E96-D, No. 7, pp.1419-1429.

%H Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch, Manfred Scheucher, and Birgit Vogtenhuber, <a href="https://arxiv.org/abs/2310.19711">Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles</a>, arXiv:2310.19711 [math.CO], 2023. See p. 41.

%H Matthew J. Samuel, <a href="http://arxiv.org/abs/1101.4655">Word posets, complexity, and Coxeter groups</a>, arXiv:1101.4655 [math.CO], 2011.

%H M. J. Samuel, <a href="http://arxiv.org/abs/1108.3638">Word posets, with applications to Coxeter groups</a>, arXiv preprint arXiv:1108.3638 [cs.DM], 2011.

%H Manfred Scheucher, <a href="/A006245/a006245.cpp.txt">C++ program for enumeration</a>

%H B. E. Tenner, <a href="https://arxiv.org/abs/1811.00082">Tiling-based models of perimeter and area</a>, arXiv:1811.00082 [math.CO], 2018.

%H M. Widom, N. Destainville, R. Mosseri and F. Bailly, <a href="https://arxiv.org/abs/cond-mat/9912275">Two-dimensional random tilings of large codimension</a>, Proceedings of the 7th International Conference on Quasicrystals (ICQ7, Stuttgart), arXiv:cond-mat/9912275 [cond-mat.stat-mech], 1999.

%H M. Widom, N. Destainville, R. Mosseri and F. Bailly, <a href="https://doi.org/10.1016/S0921-5093(00)01140-0">Two-dimensional random tilings of large codimension</a>, Materials Science and Engineering: A, Volumes 294-296, 15 December 2000, Pages 409-412.

%H Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno and Kunihiro Wasa, <a href="http://www.cs.umanitoba.ca/~cccg2018/papers/session2A-p3.pdf">Ladder-Lottery Realization</a>, 30th Canadian Conference on Computational Geometry (CCCG 2018) Winnipeg.

%H K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara and K. Nakada, <a href="https://doi.org/10.1016/j.tcs.2010.01.002">Efficient enumeration of all ladder lotteries and its application</a>, Theoretical Computer Science, Vol. 411, pp. 1714-1722, 2010.

%H G. M. Ziegler, <a href="https://www.mi.fu-berlin.de/math/groups/discgeom/ziegler/Preprintfiles/025PREPRINT.pdf">Higher Bruhat Orders and Cyclic Hyperplane Arrangements</a>, Topology, Volume 32, 1993.

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>.

%F Felsner and Valtr show that 0.1887 <= log_2(a(n))/n^2 <= 0.6571 for sufficiently large n. - _Jeremy Tan_, Nov 20 2017

%F Dumitrescu and Mandal improved the lower bound to 0.2083 <= log_2(a(n))/n^2 for sufficiently large n. - _Manfred Scheucher_, Sep 13 2021

%e This is a wiring diagram, one sample of the 62 objects that are counted for n=5:

%e 1-1-1-1 4-4 5-5

%e X X

%e 2 3-3 4 1 5 4-4

%e X X X

%e 3 2 4 3 5 1 3-3

%e X X X

%e 4-4 2 5 3-3 1 2

%e X X

%e 5-5-5 2-2-2-2 1

%e Each X denotes a comparator that exchanges the two incoming strands from the left. The whole network has n*(n-1)/2 such comparators and exchanges the order 12345 at the left edge into the reverse order 54321 at the right edge. It is also a pseudoline arrangement consisting of n x-monotone curves (from left to right), which pairwise cross exactly once.

%p # classes: Wrapper for computing number of commutation classes;

%p # pass a permutation as a list

%p # Returns number of commutation classes of reduced words

%p # Longest element is of the form [n, n-1, ..., 1] (see Comments)

%p classes:=proc(perm) option remember:

%p RETURN(classesRecurse(Array(perm), 0, 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 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=0 and doneany=0 then RETURN(1):

%p else RETURN(sums):

%p end:

%p end:

%p seq(classes([seq(n+1-i, i = 1 .. n)]), n = 1 .. 9)

%p # _Matthew J. Samuel_, Jan 23 2011, Jan 26 2011

%t classes[perm_List] := classes[perm] = classesRecurse[perm, 0, 1];

%t 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]]];

%t a[n_] := a[n] = classes[Range[n] // Reverse];

%t Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 9}] (* _Jean-François Alcover_, May 09 2017, translated from Maple *)

%Y Cf. A006246. See A005118 for primitive sorting networks with exactly one comparator ("X") per column. See A060596-A060601 for higher dimensions. Cf. A006247.

%K nonn,nice,more

%O 1,3

%A _N. J. A. Sloane_

%E More terms from Sebastien Veigneau (sv(AT)univ-mlv.fr), Jan 15 1997

%E 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.

%E a(11) from Katsuhisa Yamanaka(yamanaka(AT)hol.is.uec.ac.jp), May 06 2009

%E Reference with formula that the Maple program implements added and a(11) verified by _Matthew J. Samuel_, Jan 25 2011

%E Removed invalid comment concerning the denominators of the indicated polynomials; added a(12). - _Matthew J. Samuel_, Jan 30 2011

%E a(13) from _Toshiki Saitoh_, Oct 17 2011

%E a(14) and a(15) from _Yuma Tanaka_, Aug 20 2013

%E a(16) by _Günter Rote_, Dec 01 2021

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:36 EDT 2024. Contains 371264 sequences. (Running on oeis4.)