|
%I M1495 N0588 #183 Nov 30 2023 10:54:48
%S 1,1,2,5,16,63,318,2045,16999,183231,2567284,46749427,1104891746,
%T 33823827452,1338193159771,68275077901156,4483130665195087
%N Number of partially ordered sets ("posets") with n unlabeled elements.
%C Also number of fixed effects ANOVA models with n factors, which may be both crossed and nested.
%D G. Birkhoff, Lattice Theory, 1961, p. 4.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.
%D E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
%D J. L. Davison, Asymptotic enumeration of partial orders. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 53 (1986), 277--286. MR0885256 (88c:06001)
%D E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, pages 96ff; Vol. I, 2nd. ed., Chap. 3, pp. 241ff; Vol. 2, Problem 5.39, p. 88.
%D For further references concerning the enumeration of topologies and posets see under A001035.
%H David Wasserman, <a href="/A000112/b000112.txt">Table of n, a(n) for n = 0..16</a>
%H R. Bayon, N. Lygeros, and J.-S. Sereni, <a href="http://www.math.nthu.edu.tw/~amen/2005/040909-2.pdf">New progress in enumeration of mixed models</a>, Applied Mathematics E-Notes, 5 (2005), 60-65.
%H R. Bayon, N. Lygeros, and J.-S. Sereni, <a href="http://lbgi.fr/~sereni/Articles/BLS03.pdf">Nouveaux progrès dans l'énumération des modèles mixtes</a>, in Knowledge discovery and discrete mathematics: JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
%H Gunnar Brinkmann and Brendan D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/papers/topologies.pdf">Counting unlabeled topologies and transitive relations</a>.
%H G. Brinkmann and B. D. McKay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/McKay/mckay170.html">Counting unlabeled topologies and transitive relations</a>, J. Integer Sequences, Volume 8, 2005.
%H G. Brinkmann and B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/papers/posets.pdf">Posets on up to 16 Points</a> [On Brendan McKay's home page]
%H G. Brinkmann and B. D. McKay, <a href="http://dx.doi.org/10.1023/A:1016543307592">Posets on up to 16 Points</a>, Order 19 (2) (2002) 147-179.
%H Kim Ki-Hang Butler, <a href="https://doi.org/10.1016/0095-8956(72)90064-0">The number of partially ordered sets</a>, Journal of Combinatorial Theory, Series B 13.3 (1972): 276-289.
%H K. K.-H. Butler and G. Markowsky, <a href="http://www.laptop.maine.edu/Enumeration.pdf">Enumeration of finite topologies</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184
%H K. K.-H. Butler and G. Markowsky, <a href="/A000798/a000798_1.pdf">Enumeration of finite topologies</a>, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
%H Kim Ki-Hang Butler and Gaoacs Markowsky. <a href="https://jkms.kms.or.kr/journal/view.html?uid=1936">The number of partially ordered sets. II.</a>, J. Korean Math. Soc 11 (1974): 7-17.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H C. Chaunier, <a href="/A000112/a000112.pdf">Letter to N. J. A. Sloane, Jun 22 1993, with several attachments</a>
%H C. Chaunier and N. Lygeros, <a href="http://www.lygeros.org/0052-fr.html">The Number of Orders with Thirteen Elements</a>, Order 9:3 (1992) 203-204. [See Chaunier letter]
%H C. Chaunier and N. Lygeros, <a href="http://dx.doi.org/10.1016/0304-3975(94)90070-1">Le nombre de posets à isomorphie près ayant 12 éléments</a> Theoretical Computer Science, 123 p. 89-94, 1994.
%H C. Chaunier and N. Lygeros, <a href="http://www.lygeros.org/0049-fr.html">Progrès dans l'énumération des posets</a>, C. R. Acad. Sci. Paris 314 série I (1992) 691-694. [See Chaunier letter]
%H E. D. Cooper, <a href="/A000798/a000798.pdf">Representation and generation of finite partially ordered sets</a>, Manuscript, no date [Annotated scanned copy]
%H Gábor Czédli, <a href="https://arxiv.org/abs/2309.13783">Minimum-sized generating sets of the direct powers of free distributive lattices</a>, arXiv:2309.13783 [math.CO], 2023. See p. 14.
%H M. Erné and K. Stege, <a href="/A006870/a006870.pdf">The number of partially ordered (labeled) sets</a>, Preprint, 1989. (Annotated scanned copy)
%H Uli Fahrenberg, Christian Johansen, Georg Struth, and Ratan Bahadur Thapa, <a href="https://arxiv.org/abs/1910.06162">Generating Posets Beyond N</a>, arXiv:1910.06162 [cs.FL], 2019.
%H S. R. Finch, <a href="/A000798/a000798_12.pdf">Transitive relations, topologies and partial orders</a>, June 5, 2003. [Cached copy, with permission of the author]
%H FindStat - Combinatorial Statistic Finder, <a href="https://www.findstat.org/CollectionsDatabase/Posets/">Posets</a>
%H R. Fraisse and N. Lygeros, <a href="http://www.lygeros.org/0033-fr.html">Petits posets: dénombrement, représentabilité par cercles et compenseurs</a> C. R. Acad. Sci. Paris, 313, I, 417-420, 1991.
%H E. N. Gilbert, <a href="/A000798/a000798_9.pdf">A catalog of partially ordered systems</a>, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
%H G. Grekos, <a href="/A000112/a000112_1.pdf">Letter to N. J. A. Sloane, Oct 31 1994, with attachments</a>
%H M. Guay-Paquet, <a href="https://arxiv.org/abs/1306.2400">A modular relation for the chromatic symmetric functions of (3+1)-free posets</a>, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
%H Ann Marie Hess, <a href="http://www.stat.colostate.edu/~hess/MixedModels.htm">Mixed Models Site</a>
%H C. Joslyn, E. Hogan, and A. Pogel, <a href="https://arxiv.org/abs/1409.6684">Conjugacy and Iteration of Standard Interval Rank in Finite Ordered Sets</a>, arXiv preprint arXiv:1409.6684 [math.CO], 2014.
%H Dongseok Kim, Young Soo Kwon, and Jaeun Lee, <a href="https://arxiv.org/abs/1206.0550">Enumerations of finite topologies associated with a finite graph</a>, arXiv preprint arXiv:1206.0550 [math.CO], 2012.
%H D. J. Kleitman and B. L. Rothschild, <a href="http://dx.doi.org/10.1090/S0002-9947-1975-0369090-9">Asymptotic enumeration of partial orders on a finite set</a>, Trans. Amer. Math. Soc., 205 (1975) 205-220.
%H N. Lygeros, <a href="https://lygeros.org/26-fr/">Calculs exhaustifs sur les posets d'au plus 7 éléments</a>, SINGULARITE, vol. 2 n4 p. 10-24, avril 1991.
%H N. Lygeros and P. Zimmermann, <a href="http://opus.nysoftwarelab.gr/poset/">Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771</a>
%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
%H Bob Proctor, <a href="https://web.archive.org/web/20190905161049/http://lists-of-posets.math.unc.edu/">Chapel Hill Poset Atlas</a>
%H D. Rusin, <a href="http://www.math.niu.edu/~rusin/known-math/97/finite.top">Further information and references</a> [Broken link]
%H D. Rusin, <a href="/A000112/a000112.top.txt">Further information and references</a> [Cached copy]
%H Henry Sharp, Jr., <a href="/A001930/a001930_1.pdf">Quasi-orderings and topologies on finite sets</a>, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
%H N. J. A. Sloane, <a href="/A000112/a000112_2.pdf">List of sequences related to partial orders, circa 1972</a>
%H N. J. A. Sloane, <a href="/classic.html#POSETS">Classic Sequences</a>
%H Peter Steinbach, <a href="/A000664/a000664_10.pdf">Field Guide to Simple Graphs, Volume 4</a>, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H Szilárd Szalay, <a href="https://arxiv.org/abs/1806.04392">The classification of multipartite quantum correlation</a>, arXiv:1806.04392 [quant-ph], 2018.
%H N. L. White, <a href="/A000798/a000798_6.pdf">Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure</a>
%H J. A. Wright, <a href="/A000798/a000798_3.pdf">There are 718 6-point topologies, quasiorderings and transgraphs</a>, Preprint, 1970 [Annotated scanned copy]
%H J. A. Wright, <a href="/A000798/a000798_5.pdf">Two related abstracts, 1970 and 1972</a> [Annotated scanned copies]
%H J. A. Wright, <a href="/A000798/a000798_4.pdf">Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences</a>
%H Stav Zalel, <a href="https://arxiv.org/abs/2302.10582">Covariant Growth Dynamics</a>, arXiv:2302.10582 [gr-qc], 2023.
%H <a href="/index/Pos#posets">Index entries for sequences related to posets</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%e R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 (or 2nd. ed., Fig. 3.1, p. 243) shows the unlabeled posets with <= 4 points.
%e From _Gus Wiseman_, Aug 14 2019: (Start)
%e Also the number of unlabeled T_0 topologies with n points. For example, non-isomorphic representatives of the a(4) = 16 topologies are:
%e {}{1}{12}{123}{1234}
%e {}{1}{2}{12}{123}{1234}
%e {}{1}{12}{13}{123}{1234}
%e {}{1}{12}{123}{124}{1234}
%e {}{1}{2}{12}{13}{123}{1234}
%e {}{1}{2}{12}{123}{124}{1234}
%e {}{1}{12}{13}{123}{124}{1234}
%e {}{1}{2}{12}{13}{123}{124}{1234}
%e {}{1}{2}{12}{13}{123}{134}{1234}
%e {}{1}{2}{3}{12}{13}{23}{123}{1234}
%e {}{1}{2}{12}{13}{24}{123}{124}{1234}
%e {}{1}{12}{13}{14}{123}{124}{134}{1234}
%e {}{1}{2}{3}{12}{13}{23}{123}{124}{1234}
%e {}{1}{2}{12}{13}{14}{123}{124}{134}{1234}
%e {}{1}{2}{3}{12}{13}{14}{23}{123}{124}{134}{1234}
%e {}{1}{2}{3}{4}{12}{13}{14}{23}{24}{34}{123}{124}{134}{234}{1234}
%e (End)
%Y Cf. A000798 (labeled topologies), A001035 (labeled posets), A001930 (unlabeled topologies), A006057.
%Y Cf. A079263, A079265, A065066 (refined by maximal elements), A342447 (refined by number of arcs).
%Y Row sums of A263859. Euler transform of A000608.
%Y Cf. A316978, A319559, A326939, A326943, A326944, A326947.
%K nonn,hard,more,core,nice
%O 0,3
%A _N. J. A. Sloane_
%E a(15)-a(16) are from Brinkmann's and McKay's paper. - _Vladeta Jovovic_, Jan 04 2006
| 