The OEIS is supported by the many generous donors to the OEIS Foundation.
%I M3068 N1244 #227 Mar 10 2025 17:23:45
%S 1,1,3,19,219,4231,130023,6129859,431723379,44511042511,6611065248783,
%T 1396281677105899,414864951055853499,171850728381587059351,
%U 98484324257128207032183,77567171020440688353049939,83480529785490157813844256579,122152541250295322862941281269151,241939392597201176602897820148085023
%N Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).
%C From _Altug Alkan_, Dec 22 2015: (Start)
%C a(p^k) == 1 (mod p) and a(n + p) == a(n + 1) (mod p) for all primes p.
%C a(0+19) == a(0+1) (mod 19) or a(19^1) == 1 (mod 19), that is, a(19) mod 19 = 1.
%C a(2+17) == a(2+1) (mod 17). So a(19) == 19 (mod 17), that is, a(19) mod 17 = 2.
%C a(6+13) == a(6+1) (mod 13). So a(19) == 6129859 (mod 13), that is, a(19) mod 13 = 8.
%C a(8+11) == a(8+1) (mod 11). So a(19) == 44511042511 (mod 11), that is, a(19) mod 11 = 1.
%C a(12+7) == a(12+1) (mod 7). So a(19) == 171850728381587059351 (mod 7), that is, a(19) mod 7 = 1.
%C a(14+5) == a(14+1) (mod 5). So a(19) == 77567171020440688353049939 (mod 5), that is, a(19) mod 5 = 4.
%C a(16+3) == a(16+1) (mod 3). So a(19) == 122152541250295322862941281269151 (mod 3), that is, a(19) mod 3 = 1.
%C a(17+2) == a(17+1) (mod 2). So a(19) mod 2 = 1.
%C In conclusion, a(19) is a number of the form 2*3*5*7*11*13*17*19*n - 1615151, that is, 9699690*n - 1615151.
%C Additionally, for n > 0, note that the last digit of a(n) has the simple periodic pattern: 1,3,9,9,1,3,9,9,1,3,9,9,...
%C (End)
%C Number of rank n sublattices of the Boolean algebra B_n. - _Kevin Long_, Nov 20 2018
%C a(n) is the number of n X n idempotent Boolean relation matrices (A121337) that have rank n. - _Geoffrey Critzer_, Aug 16 2023
%C a(19) == 163279579 (mod 232792560). - _Didier Garcia_, Feb 06 2025
%D G. Birkhoff, Lattice Theory, Amer. Math. Soc., 1961, p. 4.
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 427.
%D 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.
%D 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.
%D K. K. H. Butler and G. Markowsky. "The number of partially ordered sets. I." Journal of Korean Mathematical Society 11.1 (1974).
%D S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 60, 229.
%D M. Erné, Struktur- und Anzahlformeln für Topologien auf endlichen Mengen, PhD dissertation, Westfälische Wilhelms-Universität zu Münster, 1972.
%D M. Erné and K. Stege, The number of labeled orders on fifteen elements, personal communication.
%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. 2, Problem 5.39, p. 88.
%H Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://doi.org/10.37236/12686">Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding</a>, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); <a href="https://arxiv.org/abs/2312.07716">arXiv preprint</a>, arXiv:2312.07716 [math.CO], 2023.
%H Juliana Bowles and Marco B. Caminati, <a href="https://arxiv.org/abs/1705.07228">A Verified Algorithm Enumerating Event Structures</a>, arXiv:1705.07228 [cs.LO], 2017.
%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 J. I. Brown and S. Watson, <a href="http://dx.doi.org/10.1016/0012-365X(95)00004-G">The number of complements of a topology on n points is at least 2^n (except for some special cases)</a>, Discr. Math., 154 (1996), 27-39.
%H K. K.-H. 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 K. K.-H. Butler and G. Markowsky, <a href="https://jkms.kms.or.kr/journal/view.html?uid=1936&vmd=Full">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 S. D. Chatterji, <a href="/A000798/a000798_10.pdf">The number of topologies on n points</a>, Manuscript, 1966. [Annotated scanned copy]
%H Narendrakumar R. Dasre and Pritam Gujarathi, <a href="https://doi.org/10.1007/978-981-32-9515-5_33">Approximating the Bounds for Number of Partially Ordered Sets with n Labeled Elements</a>, Computing in Engineering and Technology, Advances in Intelligent Systems and Computing, Vol. 1025, Springer (Singapore 2019), 349-356.
%H M. Erné, <a href="http://dx.doi.org/10.1007/BF01173716">Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen</a>, Manuscripta Math., 11 (1974), 221-259.
%H M. Erné, <a href="/A006056/a006056.pdf">Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen</a>, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
%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 M. Erné and K. Stege, <a href="http://dx.doi.org/10.1007/BF00383446">Counting Finite Posets and Topologies</a>, Order, 8 (1991), 247-265.
%H J. W. Evans, F. Harary and M. S. Lynn, <a href="http://dx.doi.org/10.1145/363282.363311">On the computer enumeration of finite topologies</a>, Commun. ACM, 10 (1967), 295-297, 313.
%H J. W. Evans, F. Harary and M. S. Lynn, <a href="/A000798/a000798_8.pdf"> On the computer enumeration of finite topologies</a>, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Transitive relations, topologies and partial orders</a>.
%H S. R. Finch, <a href="/A000798/a000798_12.pdf">Transitive relations, topologies and partialorders</a>, June 5, 2003. [Cached copy, with permission of the author]
%H Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, <a href="https://arxiv.org/abs/2302.08265">MC-finiteness of restricted set partition functions</a>, arXiv:2302.08265 [math.CO], 2023.
%H Didier Garcia, <a href="/A001035/a001035.pdf">Proof of a(19) formula</a> [in French].
%H Didier Garcia, <a href="/A001035/a001035_1.pdf">Two conjectures concerning a(n)</a> [in French].
%H Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.
%H G. Grekos, <a href="/A000112/a000112_1.pdf">Letter to N. J. A. Sloane, Oct 31 1994, with attachments</a>.
%H J. Heitzig and J. Reinhold, <a href="http://dx.doi.org/10.1023/A:1006431609027">The number of unlabeled orders on fourteen elements</a>, Order 17 (2000) no. 4, 333-341.
%H Richard Kenyon, Maxim Kontsevich, Oleg Ogievetsky, Cosmin Pohoata, Will Sawin, and Senya Shlosman, <a href="https://arxiv.org/abs/2401.05291">The miracle of integer eigenvalues</a>, arXiv:2401.05291 [math.CO], 2024. See p. 4.
%H Dongseok Kim, Young Soo Kwon, and Jaeun Lee, <a href="http://arxiv.org/abs/1206.0550">Enumerations of finite topologies associated with a finite graph</a>, arXiv preprint arXiv:1206.0550 [math.CO], 2012. - From _N. J. A. Sloane_, Nov 09 2012
%H M. Y. Kizmaz, <a href="http://arxiv.org/abs/1503.08359">On The Number Of Topologies On A Finite Set</a>, arXiv preprint arXiv:1503.08359 [math.NT], 2015.
%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 G. Kreweras, <a href="http://dx.doi.org/10.1016/0012-365X(85)90137-2">Dénombrement des ordres étagés</a>, Discrete Math., 53 (1985), 147-149.
%H Institut f. Mathematik, Univ. Hanover, <a href="http://www-ifm.math.uni-hannover.de/html/preprints.phtml">Erne/Heitzig/Reinhold papers</a>.
%H Sami Lazaar, Houssem Sabri, and Randa Tahri, <a href="https://doi.org/10.1007/s41980-021-00599-3">Structural and Numerical Studies of Some Topological Properties for Alexandroff Spaces</a>, Bull. Iran. Math. Soc. (2021).
%H N. Lygeros and P. Zimmermann, <a href="http://www.lygeros.org/Math/poset.html">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="http://lists-of-posets.math.unc.edu/">Chapel Hill Poset Atlas</a>.
%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%H Ivo Rosenberg, <a href="http://dx.doi.org/10.1016/0097-3165(73)90058-7">The number of maximal closed classes in the set of functions over a finite domain</a>, J. Combinatorial Theory Ser. A 14 (1973), 1-7.
%H Ivo Rosenberg and N. J. A. Sloane, <a href="/A002824/a002824_1.pdf">Correspondence, 1971</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 A. Shafaat, <a href="http://dx.doi.org/10.1017/S1446788700005231">On the number of topologies definable for a finite set</a>, J. Austral. Math. Soc., 8 (1968), 194-198.
%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="/A000112/a000112_2.pdf">List of sequences related to partial orders, circa 1972</a>.
%H N. J. A. Sloane, <a href="/classic.html#LOSS">Classic Sequences</a>.
%H Gus Wiseman, <a href="/A001035/a001035.png">Hasse diagrams of the a(4) = 219 posets</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_4.pdf">Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences</a>.
%H <a href="/index/Pos#posets">Index entries for sequences related to posets</a>
%F A000798(n) = Sum_{k=0..n} Stirling2(n,k)*a(k).
%F Related to A000112 by Erné's formulas: a(n+1) = -s(n, 1), a(n+2) = n*a(n+1) + s(n, 2), a(n+3) = binomial(n+4, 2)*a(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).
%F From _Altug Alkan_, Dec 22 2015: (Start)
%F a(p^k) == 1 (mod p) for all primes p and for all nonnegative integers k.
%F a(n + p) == a(n + 1) (mod p) for all primes p and for all nonnegative integers n.
%F If n = 1, then a(1 + p) == a(2) (mod p), that is, a(p + 1) == 3 (mod p).
%F If n = p, then a(p + p) == a(p + 1) (mod p), that is, a(2*p) == a(p + 1) (mod p).
%F In conclusion, a(2*p) == 3 (mod p) for all primes p.
%F (End)
%F a(n) = Sum_{k=0..n} Stirling1(n,k)*A000798(k). - _Tian Vlasic_, Feb 25 2022
%e R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 shows the unlabeled posets with <= 4 points.
%e From _Gus Wiseman_, Aug 14 2019: (Start)
%e Also the number of T_0 topologies with n points. For example, the a(0) = 1 through a(3) = 19 topologies are:
%e {} {}{1} {}{1}{12} {}{1}{12}{123}
%e {}{2}{12} {}{1}{13}{123}
%e {}{1}{2}{12} {}{2}{12}{123}
%e {}{2}{23}{123}
%e {}{3}{13}{123}
%e {}{3}{23}{123}
%e {}{1}{2}{12}{123}
%e {}{1}{3}{13}{123}
%e {}{2}{3}{23}{123}
%e {}{1}{12}{13}{123}
%e {}{2}{12}{23}{123}
%e {}{3}{13}{23}{123}
%e {}{1}{2}{12}{13}{123}
%e {}{1}{2}{12}{23}{123}
%e {}{1}{3}{12}{13}{123}
%e {}{1}{3}{13}{23}{123}
%e {}{2}{3}{12}{23}{123}
%e {}{2}{3}{13}{23}{123}
%e {}{1}{2}{3}{12}{13}{23}{123}
%e (End)
%t dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
%t Table[Length[Select[Subsets[Subsets[Range[n]]],MemberQ[#,{}]&&MemberQ[#,Range[n]]&&UnsameQ@@dual[#]&&SubsetQ[#,Union@@@Tuples[#,2]]&&SubsetQ[#,Intersection@@@Tuples[#,2]]&]],{n,0,3}] (* _Gus Wiseman_, Aug 14 2019 *)
%Y Cf. A000798 (labeled topologies), A001930 (unlabeled topologies), A000112 (unlabeled posets), A006057.
%Y Sequences in the Erné (1974) paper: A000798, A001035, A006056, A006057, A001929, A001927, A006058, A006059, A000110.
%Y Cf. A316978, A319564, A326876, A326906, A326939, A326943, A326944, A326947.
%K nonn,nice,changed
%O 0,3
%A _N. J. A. Sloane_
%E a(15)-a(16) from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000
%E a(17)-a(18) from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008