0,3

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

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.

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.

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

Jason I. Brown and Stephen 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.

Kim Ki-Hang Butler, The number of partially ordered sets, J. Combin. Theory, Series B 13.3 (1972): 276-289.

Kim Ki-Hang Butler and George Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.

Kim Ki-Hang Butler and George 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 George Markowsky, The number of partially ordered sets. II., J. Korean Math. Soc 11 (1974): 7-17.

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

Marcel Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.

Marcel Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)

Marcel Erné and Kurt Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)

Marcel Erné and Kurt 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]

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

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

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

Jobst Heitzig and Jürgen 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

Muhammet Yasir Kızmaz, 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.

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

Jason Lo and Mohammadnima Jafari, From data to concepts via wiring diagrams, arXiv:2511.20138 [cs.AI], 2025. See pp. 6, 11.

N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771.

Adam Olszewski, Simple remarks on counting posets on an n-element set, ResearchGate (2025). See p. 5.

Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Bob Proctor, Chapel Hill Poset Atlas.

Yash Puri and Thomas 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. Combin. Theory Ser. A 14 (1973), 1-7.

Ivo Rosenberg and N. J. A. Sloane, Correspondence, 1971.

D. Rusin, Further information and references.

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.

John A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970. [Annotated scanned copy]

John A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences.

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

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)

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

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.

Sequence in context: A158876 A378326 A001833 * A267634 A277407 A271587

Adjacent sequences: A001032 A001033 A001034 * A001036 A001037 A001038

nonn,nice

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

approved