A001035 Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs).

1, 1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579, 122152541250295322862941281269151, 241939392597201176602897820148085023

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

From Altug Alkan, Dec 22 2015: (Start)

a(p^k) == 1 (mod p) and a(n + p) == a(n + 1) (mod p) for all primes p.

a(0+19) == a(0+1) (mod 19) or a(19^1) == 1 (mod 19), that is, a(19) mod 19 = 1.

a(2+17) == a(2+1) (mod 17). So a(19) == 19 (mod 17), that is, a(19) mod 17 = 2.

a(6+13) == a(6+1) (mod 13). So a(19) == 6129859 (mod 13), that is, a(19) mod 13 = 8.

a(8+11) == a(8+1) (mod 11). So a(19) == 44511042511 (mod 11), that is, a(19) mod 11 = 1.

a(12+7) == a(12+1) (mod 7). So a(19) == 171850728381587059351 (mod 7), that is, a(19) mod 7 = 1.

a(14+5) == a(14+1) (mod 5). So a(19) == 77567171020440688353049939 (mod 5), that is, a(19) mod 5 = 4.

a(16+3) == a(16+1) (mod 3). So a(19) == 122152541250295322862941281269151 (mod 3), that is, a(19) mod 3 = 1.

a(17+2) == a(17+1) (mod 2). So a(19) mod 2 = 1.

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.

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,...

(End)

Number of rank n sublattices of the Boolean algebra B_n. - Kevin Long, Nov 20 2018

a(n) is the number of n X n idempotent Boolean relation matrices (A121337) that have rank n. - Geoffrey Critzer, Aug 16 2023

a(19) == 163279579 (mod 232792560). - Didier Garcia, Feb 06 2025

Examples

			R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 shows the unlabeled posets with <= 4 points.
From _Gus Wiseman_, Aug 14 2019: (Start)
Also the number of T_0 topologies with n points. For example, the a(0) = 1 through a(3) = 19 topologies are:
  {}  {}{1}  {}{1}{12}     {}{1}{12}{123}
             {}{2}{12}     {}{1}{13}{123}
             {}{1}{2}{12}  {}{2}{12}{123}
                           {}{2}{23}{123}
                           {}{3}{13}{123}
                           {}{3}{23}{123}
                           {}{1}{2}{12}{123}
                           {}{1}{3}{13}{123}
                           {}{2}{3}{23}{123}
                           {}{1}{12}{13}{123}
                           {}{2}{12}{23}{123}
                           {}{3}{13}{23}{123}
                           {}{1}{2}{12}{13}{123}
                           {}{1}{2}{12}{23}{123}
                           {}{1}{3}{12}{13}{123}
                           {}{1}{3}{13}{23}{123}
                           {}{2}{3}{12}{23}{123}
                           {}{2}{3}{13}{23}{123}
                           {}{1}{2}{3}{12}{13}{23}{123}
(End)
		

References

• G. Birkhoff, Lattice Theory, Amer. Math. Soc., 1961, p. 4.
• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 427.
• 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.
• K. K. H. Butler and G. Markowsky. "The number of partially ordered sets. I." Journal of Korean Mathematical Society 11.1 (1974).
• S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.
• L. Comtet, Advanced Combinatorics, Reidel, 1974, pp. 60, 229.
• M. Erné, Struktur- und Anzahlformeln für Topologien auf endlichen Mengen, PhD dissertation, Westfälische Wilhelms-Universität zu Münster, 1972.
• M. Erné and K. Stege, The number of labeled orders on fifteen elements, personal communication.
• 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.

Links

• Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, arXiv:2312.07716 [math.CO], 2023.
• Juliana Bowles and Marco B. Caminati, A Verified Algorithm Enumerating Event Structures, arXiv:1705.07228 [cs.LO], 2017.
• G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
• 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, 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]
• K. K.-H. Butler and G. 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.
• S. D. Chatterji, The number of topologies on n points, Manuscript, 1966. [Annotated scanned copy]
• Narendrakumar R. Dasre and Pritam Gujarathi, Approximating the Bounds for Number of Partially Ordered Sets with n Labeled Elements, Computing in Engineering and Technology, Advances in Intelligent Systems and Computing, Vol. 1025, Springer (Singapore 2019), 349-356.
• M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
• M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
• M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
• M. Erné and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.
• J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313.
• J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]
• S. R. Finch, Transitive relations, topologies and partial orders.
• S. R. Finch, Transitive relations, topologies and partialorders, June 5, 2003. [Cached copy, with permission of the author]
• Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.
• Didier Garcia, Proof of a(19) formula [in French].
• Didier Garcia, Two conjectures concerning a(n) [in French].
• Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
• G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments.
• J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.
• Richard Kenyon, Maxim Kontsevich, Oleg Ogievetsky, Cosmin Pohoata, Will Sawin, and Senya Shlosman, The miracle of integer eigenvalues, arXiv:2401.05291 [math.CO], 2024. See p. 4.
• 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. - From _N. J. A. Sloane_, Nov 09 2012
• M. Y. Kizmaz, On The Number Of Topologies On A Finite Set, arXiv preprint arXiv:1503.08359 [math.NT], 2015.
• 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, Dénombrement des ordres étagés, Discrete Math., 53 (1985), 147-149.
• Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers.
• Sami Lazaar, Houssem Sabri, and Randa Tahri, Structural and Numerical Studies of Some Topological Properties for Alexandroff Spaces, Bull. Iran. Math. Soc. (2021).
• 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.
• Ivo Rosenberg, The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 1-7.
• Ivo Rosenberg and N. J. A. Sloane, Correspondence, 1971.
• D. Rusin, Further information and references. [Broken link]
• D. Rusin, Further information and references. [Cached copy]
• A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198.
• N. J. A. Sloane, List of sequences related to partial orders, circa 1972.
• N. J. A. Sloane, List of sequences related to partial orders, circa 1972.
• N. J. A. Sloane, Classic Sequences.
• Gus Wiseman, Hasse diagrams of the a(4) = 219 posets.
• J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970. [Annotated scanned copy]
• J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences.
• Index entries for sequences related to posets

Crossrefs

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

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

Cf. A316978, A319564, A326876, A326906, A326939, A326943, A326944, A326947.

Programs

Mathematica

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
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 *)

Formula

A000798(n) = Sum_{k=0..n} Stirling2(n,k)*a(k).

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).

From Altug Alkan, Dec 22 2015: (Start)

a(p^k) == 1 (mod p) for all primes p and for all nonnegative integers k.

a(n + p) == a(n + 1) (mod p) for all primes p and for all nonnegative integers n.

If n = 1, then a(1 + p) == a(2) (mod p), that is, a(p + 1) == 3 (mod p).

If n = p, then a(p + p) == a(p + 1) (mod p), that is, a(2*p) == a(p + 1) (mod p).

In conclusion, a(2*p) == 3 (mod p) for all primes p.

(End)

a(n) = Sum_{k=0..n} Stirling1(n,k)*A000798(k). - Tian Vlasic, Feb 25 2022

Extensions

a(15)-a(16) from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

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