A001930 Number of topologies, or transitive digraphs with n unlabeled nodes.

1, 1, 3, 9, 33, 139, 718, 4535, 35979, 363083, 4717687, 79501654, 1744252509, 49872339897, 1856792610995, 89847422244493, 5637294117525695

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• hard
• more
• nice

Examples

			From _Gus Wiseman_, Aug 02 2019: (Start)
Non-isomorphic representatives of the a(0) = 1 through a(3) = 9 topologies:
  {}  {}{1}  {}{12}        {}{123}
             {}{2}{12}     {}{3}{123}
             {}{1}{2}{12}  {}{23}{123}
                           {}{1}{23}{123}
                           {}{3}{23}{123}
                           {}{2}{3}{23}{123}
                           {}{3}{13}{23}{123}
                           {}{2}{3}{13}{23}{123}
                           {}{1}{2}{3}{12}{13}{23}{123}
(End)
		

References

• Loic Foissy, Claudia Malvenuto, 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. .
• F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218 (but the last entry is wrong).
• M. Kolli, On the cardinality of the T_0-topologies on a finite set, Preprint, 2014.
• 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).
• J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.
• J. A. Wright, personal communication.
• For further references concerning the enumeration of topologies and posets see under A000112 and A001035.

Links

• C. M. Bender et al., Combinatorics and field theory, arXiv:quant-ph/0604164, 2006.
• Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.
• M. Benoumhani and M. Kolli, Finite topologies and partitions, JIS 13 (2010) # 10.3.5
• Gunnar Brinkmann and Brendan D. McKay, Counting unlabeled topologies and transitive relations.
• G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
• Gunnar Brinkmann and Brendan D. McKay, Counting Unlabelled Topologies and Transitive Relations, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.1.
• 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]
• 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
• S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
• L. Foissy, C. Malvenuto, and F. Patras, B_infinity-algebras, their enveloping algebras, and finite spaces, arXiv preprint arXiv:1403.7488 [math.AT], 2014-2015.
• Misha Gavrilovich and Misha Rabinovich, The Quillen negation monoid of a category, and Schreier graphs of its action on classes of morphisms, 2024. See p. 11.
• 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
• Messaoud Kolli, Direct and Elementary Approach to Enumerate Topologies on a Finite Set, J. Integer Sequences, Volume 10, 2007, Article 07.3.1.
• G. Pfeiffer, Counting Transitive Relations, preprint, 2004.
• G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
• D. Rusin, Further information and references [Broken link]
• D. Rusin, Further information and references [Cached copy]
• Henry Sharp, Jr., Quasi-orderings and topologies on finite sets, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
• 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.
• J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
• R. H. Warren, The number of topologies, Houston J. Math., 8 (No. 2, 1982), 297-301. Mentions a(4)=33. [Annotated scanned copy]
• Eric Weisstein's World of Mathematics, Digraph Topology.
• R. H. Warren, The number of topologies, Houston J. Math., 8 (No. 2, 1982), 297-301. Mentions a(4)=33. [Annotated scanned copy]
• Wikipedia Topological space
• 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

Crossrefs

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

The case with unions only is A108798.

The case with intersections only is (also) A108798.

Partial sums are A326898 (the non-covering case).

Cf. A000612, A003180, A108800, A193674, A306445, A326876, A326878, A326882.

Extensions

a(8)-a(12) from Goetz Pfeiffer (goetz.pfeiffer(AT)nuigalway.ie), Jan 21 2004

a(13)-a(16) from Brinkmann's and McKay's paper, sent by Vladeta Jovovic, Jan 04 2006