This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001035 Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).
(Formerly M3068 N1244)
1, 1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579, 122152541250295322862941281269151, 241939392597201176602897820148085023 (list; graph; refs; listen; history; text; internal format)



G. Birkhoff, Lattice Theory, Amer. Math. Soc., 1961, p. 4.

J. I. Brown and S. Watson, The number of complements of a topology on n points is at least 2^n (except for some special cases), Discr. Math., 154 (1996), 27-39.

K. K.-H. Butler, A Moore-Penrose inverse for Boolean relation matrices, pp. 18-28 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.

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.

S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.

L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 60, 229.

M. Erne, Struktur- und Anzahlformeln fuer Topologien auf endlichen Mengen, PhD dissertation, Westfaelische Wilhelms-Universitaet zu Muenster, 1972.

M. Erne', Struktur- und Anzahlformeln fuer Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.

M. Erne and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.

M. Erne and K. Stege, The number of labeled orders on fifteen elements, personal communication.

J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313.

J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.

D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.

G. Kreweras, Denombrement des ordres etages, Discrete Math., 53 (1985), 147-149.

A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198.

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. 2, Problem 5.39, p. 88.


Table of n, a(n) for n=0..18.

G. Brinkmann,  B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

S. R. Finch, Transitive relations, topologies and partial orders

G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments

DONGSEOK KIM, YOUNG SOO KWON AND JAEUN LEE, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550, 2012. - From N. J. A. Sloane, Nov 09 2012

Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers

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

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Rosenberg, Ivo; The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 1-7.

D. Rusin, Number of topologies

N. J. A. Sloane, Classic Sequences

Index entries for sequences related to posets


Related to A000798 by A000798(n) = Sum Stirling2(n, k)*A001035(k).

Related to A000112 by Erne's formulae: A001035(n+1)=-s(n, 1), A001035(n+2)=n*A001035(n+1)+s(n, 2), A001035(n+3)=binomial(n+4, 2)*A001035(n+2)-s(n, 3), where s(n, k)=sum(binomial(n+k-1-m, k-1)*binomial(n+k, m)*sum((m!)/(number of automorphisms of P)*(-(number of antichains of P))^k, P an unlabeled poset with m elements), m=0..n).


R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 shows the unlabeled posets with <= 4 points.


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

Sequences in the Erne' (1974) paper: A000798, A001035, A006056, A006057, A001929, A001927, A006058, A006059, A000110.

Sequence in context: A005647 A158876 A001833 * A217906 A166380 A136652

Adjacent sequences:  A001032 A001033 A001034 * A001036 A001037 A001038




N. J. A. Sloane.


Terms for n=15 and 16 from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

a(17) and a(18) from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008



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

Content is available under The OEIS End-User License Agreement .

Last modified August 5 00:12 EDT 2015. Contains 260304 sequences.