A000798 Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.

1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021, 207881393656668953041, 115617051977054267807460, 88736269118586244492485121, 93411113411710039565210494095, 134137950093337880672321868725846, 261492535743634374805066126901117203

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• core
• hard

Comments

From Altug Alkan, Dec 18 2015 and Feb 28 2017: (Start)

a(p^k) == k+1 (mod p) for all primes p. This is proved by Kizmaz at On The Number Of Topologies On A Finite Set link. For proof see Theorem 2.4 in page 2 and 3. So a(19) == 2 (mod 19).

a(p+n) == A265042(n) (mod p) for all primes p. This is also proved by Kizmaz at related link, see Theorem 2.7 in page 4. If n=2 and p=17, a(17+2) == A265042(2) (mod 17), that is a(19) == 51 (mod 17). So a(19) is divisible by 17.

In conclusion, a(19) is a number of the form 323*n - 17. (End)

The BII-numbers of finite topologies without their empty set are given by A326876. - Gus Wiseman, Aug 01 2019

From Tian Vlasic, Feb 23 2022: (Start)

Although no general formula is known for a(n), by considering the number of topologies with a fixed number of open sets, it is possible to explicitly represent the sequence in terms of Stirling numbers of the second kind.

For example: a(n,3) = 2*S(n,2), a(n,4) = S(n,2) + 6*S(n,3), a(n,5) = 6*S(n,3) + 24*S(n,4).

Lower and upper bounds are known: 2^n <= a(n) <= 2^(n*(n-1)), n > 1.

This follows from the fact that there are 2^(n*(n-1)) reflexive relations on a set with n elements.

Furthermore: a(n+1) <= a(n)*(3a(n)+1). (End)

Examples

			From _Gus Wiseman_, Aug 01 2019: (Start)
The a(3) = 29 topologies are the following (empty sets not shown):
  {123}  {1}{123}   {1}{12}{123}  {1}{2}{12}{123}   {1}{2}{12}{13}{123}
         {2}{123}   {1}{13}{123}  {1}{3}{13}{123}   {1}{2}{12}{23}{123}
         {3}{123}   {1}{23}{123}  {2}{3}{23}{123}   {1}{3}{12}{13}{123}
         {12}{123}  {2}{12}{123}  {1}{12}{13}{123}  {1}{3}{13}{23}{123}
         {13}{123}  {2}{13}{123}  {2}{12}{23}{123}  {2}{3}{12}{23}{123}
         {23}{123}  {2}{23}{123}  {3}{13}{23}{123}  {2}{3}{13}{23}{123}
                    {3}{12}{123}
                    {3}{13}{123}        {1}{2}{3}{12}{13}{23}{123}
                    {3}{23}{123}
(End)
		

References

• 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, p. 229.
• E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
• E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 243.
• Levinson, H.; Silverman, R. Topologies on finite sets. II. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 699--712, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561090 (81c:54006)
• 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).
• For further references concerning the enumeration of topologies and posets see under A001035.
• G.H. Patil and M.S. Chaudhary, A recursive determination of topologies on finite sets, Indian Journal of Pure and Applied Mathematics, 26, No. 2 (1995), 143-148.

Links

• V. I. Arnautov and A. V. Kochina, Method for constructing one-point expansions of a topology on a finite set and its applications, Bul. Acad. Stiinte Republ. Moldav. Matem. 3 (64) (2010) 67-76.
• Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.
• Moussa Benoumhani and Ali Jaballah, Chains in lattices of mappings and finite fuzzy topological spaces, Journal of Combinatorial Theory, Series A (2019) Vol. 161, 99-111.
• M. Benoumhani and M. Kolli, Finite topologies and partitions, JIS 13 (2010) # 10.3.5.
• 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.
• G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179 (Table IV).
• 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 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]
• S. D. Chatterji, The number of topologies on n points, Manuscript, 1966 [Annotated scanned copy]
• Tyler Clark and Tom Richmond, The Number of Convex Topologies on a Finite Totally Ordered Set, 2013, Involve, Vol. 8 (2015), No. 1, 25-32.
• E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date [Annotated scanned copy]
• 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. [Annotated scanned copy]
• J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313.
• S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
• Loic Foissy, Claudia Malvenuto, and Frederic Patras, B_infinity-algebras, their enveloping algebras, and finite spaces, arXiv preprint arXiv:1403.7488 [math.AT], 2014.
• Loic Foissy, Claudia Malvenuto, and Frederic Patras, Infinitesimal and B_infinity-algebras, finite spaces, and quasi-symmetric functions, Journal of Pure and Applied Algebra, Elsevier, 2016, 220 (6), pp. 2434-2458. .
• L. Foissy and C. Malvenuto, The Hopf algebra of finite topologies and T-partitions, arXiv preprint arXiv:1407.0476 [math.RA], 2014.
• Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
• E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
• S. Giraudo, J.-G. Luque, L. Mignot and F. Nicart, Operads, quasiorders and regular languages, arXiv preprint arXiv:1401.2010 [cs.FL], 2014.
• D. J. Greenhoe, Properties of distance spaces with power triangle inequalities, ResearchGate, 2015.
• J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.
• Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers
• G. A. Kamel, Partial Chain Topologies on Finite Sets, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.
• 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.
• M. Y. Kizmaz, On The Number Of Topologies On A Finite Set, arXiv preprint arXiv:1503.08359 [math.NT], 2015-2019.
• D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
• D. J. Kleitman and B. L. Rothschild, The number of finite topologies, Proc. Amer. Math. Soc., 25 (1970), 276-282.
• Messaoud Kolli, Direct and Elementary Approach to Enumerate Topologies on a Finite Set, J. Integer Sequences, Volume 10, 2007, Article 07.3.1.
• Messaoud Kolli, On the cardinality of the T_0-topologies on a finite set, International Journal of Combinatorics, Volume 2014 (2014), Article ID 798074, 7 pages.
• Sami Lazaar, Houssem Sabri, and Randa Tahri, Structural and Numerical Studies of Some Topological Properties for Alexandroff Spaces, Bull. Iran. Math. Soc. (2021).
• Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
• M. Rayburn, On the Borel fields of a finite set, Proc. Amer. Math.. Soc., 19 (1968), 885-889. [Annotated scanned copy]
• M. Rayburn and N. J. A. Sloane, Correspondence, 1974
• D. Rusin, More info and references [Broken link]
• D. Rusin, More info and references [Cached copy]
• A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198. [Annotated scanned 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, Classic Sequences
• Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 8 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
• Eric Swartz and Nicholas J. Werner, Zero pattern matrix rings, reachable pairs in digraphs, and Sharp's topological invariant tau, arXiv:1709.05390 [math.CO], 2017.
• Ivo Terek, Smooth Manifolds, Williams College (2025). See p. 6.
• Wietske Visser, Koen V. Hindriks and Catholijn M. Jonker, Goal-based Qualitative Preference Systems, 2012.
• N. L. White, Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure
• J. A. Wright, Letter to N. J. A. Sloane, Nov 21 1970, with four enclosures
• 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
• Index entries for "core" sequences

Crossrefs

Row sums of A326882.

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

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

Cf. A102894, A102895, A102897, A306445, A326866, A326876, A326878, A326881.

Programs

Mathematica

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&SubsetQ[#,Union[Union@@@Tuples[#,2],DeleteCases[Intersection@@@Tuples[#,2],{}]]]&]],{n,0,3}] (* Gus Wiseman, Aug 01 2019 *)

Formula

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

E.g.f.: A(exp(x) - 1) where A(x) is the e.g.f. for A001035. - Geoffrey Critzer, Jul 28 2014

It is known that log_2(a(n)) ~ n^2/4. - Tian Vlasic, Feb 23 2022

Extensions

Two more terms from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

a(17)-a(18) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jun 10 2007