A000112 Number of partially ordered sets ("posets") with n unlabeled elements. (Formerly M1495 N0588)

1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087

Offset

0,3

Comments

Also number of fixed effects ANOVA models with n factors, which may be both crossed and nested.

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]

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

Example

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)

Crossrefs

Cf. A000798 (labeled topologies), A001035 (labeled posets), A001930 (unlabeled topologies), A006057.

Cf. A079263, A079265, A065066 (refined by maximal elements), A342447 (refined by number of arcs).

Row sums of A263859. Euler transform of A000608.

Cf. A316978, A319559, A326939, A326943, A326944, A326947.

Sequence in context: A345673 A079566 A059685 * A205498 A295131 A178119

Adjacent sequences: A000109 A000110 A000111 * A000113 A000114 A000115

Keyword

nonn,hard,more,core,nice

Author

N. J. A. Sloane

Extensions

a(15)-a(16) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jan 04 2006

Status

approved