A000112 Number of partially ordered sets ("posets") with n unlabeled elements.
1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087
Offset: 0
Examples
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.
From _Gus Wiseman_, Aug 14 2019: (Start)
Also the number of unlabeled T_0 topologies with n points. For example, non-isomorphic representatives of the a(4) = 16 topologies are:
{}{1}{12}{123}{1234}
{}{1}{2}{12}{123}{1234}
{}{1}{12}{13}{123}{1234}
{}{1}{12}{123}{124}{1234}
{}{1}{2}{12}{13}{123}{1234}
{}{1}{2}{12}{123}{124}{1234}
{}{1}{12}{13}{123}{124}{1234}
{}{1}{2}{12}{13}{123}{124}{1234}
{}{1}{2}{12}{13}{123}{134}{1234}
{}{1}{2}{3}{12}{13}{23}{123}{1234}
{}{1}{2}{12}{13}{24}{123}{124}{1234}
{}{1}{12}{13}{14}{123}{124}{134}{1234}
{}{1}{2}{3}{12}{13}{23}{123}{124}{1234}
{}{1}{2}{12}{13}{14}{123}{124}{134}{1234}
{}{1}{2}{3}{12}{13}{14}{23}{123}{124}{134}{1234}
{}{1}{2}{3}{4}{12}{13}{14}{23}{24}{34}{123}{124}{134}{234}{1234}
(End)
References
- G. Birkhoff, Lattice Theory, 1961, p. 4.
- L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.
- E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
- 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)
- E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- 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.
- For further references concerning the enumeration of topologies and posets see under A001035.
Links
- David Wasserman, Table of n, a(n) for n = 0..16
- R. Bayon, N. Lygeros, and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
- R. Bayon, N. Lygeros, and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics: JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
- Gunnar Brinkmann and Brendan D. McKay, Counting unlabeled topologies and transitive relations.
- G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
- G. Brinkmann and B. D. McKay, Posets on up to 16 Points [On Brendan McKay's home page]
- G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
- Kim Ki-Hang Butler, The number of partially ordered sets, Journal of Combinatorial Theory, Series B 13.3 (1972): 276-289.
- K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184
- K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
- Kim Ki-Hang Butler and Gaoacs Markowsky. The number of partially ordered sets. II., J. Korean Math. Soc 11 (1974): 7-17.
- P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
- C. Chaunier, Letter to N. J. A. Sloane, Jun 22 1993, with several attachments
- C. Chaunier and N. Lygeros, The Number of Orders with Thirteen Elements, Order 9:3 (1992) 203-204. [See Chaunier letter]
- C. Chaunier and N. Lygeros, Le nombre de posets à isomorphie près ayant 12 éléments Theoretical Computer Science, 123 p. 89-94, 1994.
- C. Chaunier and N. Lygeros, Progrès dans l'énumération des posets, C. R. Acad. Sci. Paris 314 série I (1992) 691-694. [See Chaunier letter]
- E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date [Annotated scanned copy]
- Gábor Czédli, Minimum-sized generating sets of the direct powers of free distributive lattices, arXiv:2309.13783 [math.CO], 2023. See p. 14. See also CUBO, A Mathematical Journal, Vol. 26, no. 2, pp. 217-237, August 2024.
- M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
- Uli Fahrenberg, Christian Johansen, Georg Struth, and Ratan Bahadur Thapa, Generating Posets Beyond N, arXiv:1910.06162 [cs.FL], 2019.
- S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
- FindStat - Combinatorial Statistic Finder, Posets
- R. Fraisse and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et compenseurs C. R. Acad. Sci. Paris, 313, I, 417-420, 1991.
- E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
- G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments
- M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
- Ann Marie Hess, Mixed Models Site
- C. Joslyn, E. Hogan, and A. Pogel, Conjugacy and Iteration of Standard Interval Rank in Finite Ordered Sets, arXiv preprint arXiv:1409.6684 [math.CO], 2014.
- Dongseok Kim, Young Soo Kwon, and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012.
- D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.
- N. Lygeros, Calculs exhaustifs sur les posets d'au plus 7 éléments, SINGULARITE, vol. 2 n4 p. 10-24, avril 1991.
- N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771
- G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
- Bob Proctor, Chapel Hill Poset Atlas
- D. Rusin, Further information and references [Broken link]
- D. Rusin, Further information and references [Cached copy]
- Henry Sharp, Jr., Quasi-orderings and topologies on finite sets, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
- N. J. A. Sloane, List of sequences related to partial orders, circa 1972
- N. J. A. Sloane, Classic Sequences
- Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
- Szilárd Szalay, The classification of multipartite quantum correlation, arXiv:1806.04392 [quant-ph], 2018.
- N. L. White, Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure
- J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]
- J. A. Wright, Two related abstracts, 1970 and 1972 [Annotated scanned copies]
- J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
- Stav Zalel, Covariant Growth Dynamics, arXiv:2302.10582 [gr-qc], 2023.
- Index entries for sequences related to posets
- Index entries for "core" sequences
Crossrefs
Extensions
a(15)-a(16) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jan 04 2006
Comments