This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000798 Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.
(Formerly M3631 N1476)

%I M3631 N1476

%S 1,1,4,29,355,6942,209527,9535241,642779354,63260289423,8977053873043,

%T 1816846038736192,519355571065774021,207881393656668953041,

%U 115617051977054267807460,88736269118586244492485121,93411113411710039565210494095,134137950093337880672321868725846,261492535743634374805066126901117203

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

%C From _Altug Alkan_, Dec 18 2015: (Start)

%C 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.

%C 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.

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

%C (End) [Edited by _Altug Alkan_, Feb 28 2017]

%C The BII-numbers of finite topologies without their empty set are given by A326876. - _Gus Wiseman_, Aug 01 2019

%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 S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 229.

%D E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.

%D E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 243.

%D 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)

%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 For further references concerning the enumeration of topologies and posets see under A001035.

%H V. I. Arnautov, A. V. Kochina, <a href="http://www.math.md/publications/basm/issues/y2010-n3/10375/">Method for constructing one-point expansions of a topology on a finite set and its applications</a>, Bul. Acad. Stiinte Republ. Moldav. Matem. 3 (64) (2010) 67-76

%H Moussa Benoumhani, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Benoumhani/benoumhani11.html">The Number of Topologies on a Finite Set</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.

%H Moussa Benoumhani, Ali Jaballah, <a href="https://doi.org/10.1016/j.jcta.2018.07.007">Chains in lattices of mappings and finite fuzzy topological spaces</a>, Journal of Combinatorial Theory, Series A (2019) Vol. 161, 99-111.

%H M. Benoumhani, M. Kolli, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Benoumhani/benoumhani6.html">Finite topologies and partitions</a>, JIS 13 (2010) # 10.3.5

%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 Gunnar Brinkmann and Brendan D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/papers/posets.pdf">Posets on up to 16 points</a>.

%H G. Brinkmann, 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 (Table IV).

%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 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 S. D. Chatterji, <a href="/A000798/a000798_10.pdf">The number of topologies on n points</a>, Manuscript, 1966 [Annotated scanned copy]

%H Tyler Clark and Tom Richmond, <a href="http://dx.doi.org/10.2140/involve.2015.8.25">The Number of Convex Topologies on a Finite Totally Ordered Set</a>, 2013, Involve, Vol. 8 (2015), No. 1, 25-32.

%H E. D. Cooper, <a href="/A000798/a000798.pdf">Representation and generation of finite partially ordered sets</a>, Manuscript, no date [Annotated scanned copy]

%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="/A000798/a000798_8.pdf"> On the computer enumeration of finite topologies</a>, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]

%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 S. R. Finch, <a href="/A000798/a000798_12.pdf">Transitive relations, topologies and partial orders</a>, June 5, 2003. [Cached copy, with permission of the author]

%H L. Foissy, C. Malvenuto, F. Patras, <a href="http://arxiv.org/abs/1403.7488">B_infinity-algebras, their enveloping algebras, and finite spaces</a>, arXiv preprint arXiv:1403.7488 [math.AT], 2014.

%H Loic Foissy, Claudia Malvenuto, Frederic Patras, <a href="http://dx.doi.org/10.1016/j.jpaa.2015.11.014">Infinitesimal and B_infinity-algebras, finite spaces, and quasi-symmetric functions</a>, Journal of Pure and Applied Algebra, Elsevier, 2016, 220 (6), pp. 2434-2458. <hal-00967351v2>.

%H L. Foissy and C. Malvenuto, <a href="http://arxiv.org/abs/1407.0476">The Hopf algebra of finite topologies and T-partitions</a>, arXiv preprint arXiv:1407.0476 [math.RA], 2014.

%H Joël Gay, Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.

%H E. N. Gilbert, <a href="/A000798/a000798_9.pdf">A catalog of partially ordered systems</a>, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]

%H S. Giraudo, J.-G. Luque, L. Mignot and F. Nicart, <a href="http://arxiv.org/abs/1401.2010">Operads, quasiorders and regular languages</a>, arXiv preprint arXiv:1401.2010 [cs.FL], 2014.

%H D. J. Greenhoe, <a href="https://www.researchgate.net/profile/Daniel_Greenhoe/publication/281831459_Properties_of_distance_spaces_with_power_triangle_inequalities">Properties of distance spaces with power triangle inequalities</a>, ResearchGate, 2015.

%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 Institut f. Mathematik, Univ. Hanover, <a href="http://www-ifm.math.uni-hannover.de/html/preprints.phtml">Erne/Heitzig/Reinhold papers</a>

%H G. A. Kamel, <a href="http://www.aascit.org/journal/archive2?journalId=928&amp;paperId=2310">Partial Chain Topologies on Finite Sets</a>, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.

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

%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, 2015

%H D. A. Klarner, <a href="/A000798/a000798_11.pdf">The number of graded partially ordered sets</a>, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]

%H D. J. Kleitman and B. L. Rothschild, <a href="http://dx.doi.org/10.1090/S0002-9939-1970-0253944-9">The number of finite topologies</a>, Proc. Amer. Math. Soc., 25 (1970), 276-282.

%H Messaoud Kolli, <a href="http://www.emis.de/journals/JIS/VOL10/Kolli/messaoud30.html">Direct and Elementary Approach to Enumerate Topologies on a Finite Set</a>, J. Integer Sequences, Volume 10, 2007, Article 07.3.1.

%H Messaoud Kolli, <a href="http://dx.doi.org/10.1155/2014/798074">On the cardinality of the T_0-topologies on a finite set</a>, International Journal of Combinatorics, Volume 2014 (2014), Article ID 798074, 7 pages.

%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 M. Rayburn, <a href="/A000110/a000110_1.pdf">On the Borel fields of a finite set</a>, Proc. Amer. Math.. Soc., 19 (1968), 885-889. [Annotated scanned copy]

%H M. Rayburn and N. J. A. Sloane, <a href="/A000110/a000110.pdf">Correspondence, 1974</a>

%H D. Rusin, <a href="http://www.math.niu.edu/~rusin/known-math/97/finite.top">More info and references</a> [Broken link]

%H D. Rusin, <a href="/A000798/a000798.txt">More info and references</a> [Cached copy]

%H A. Shafaat, <a href="/A000798/a000798_7.pdf">On the number of topologies definable for a finite set</a>, J. Austral. Math. Soc., 8 (1968), 194-198. [Annotated scanned 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="/classic.html#POSETS">Classic Sequences</a>

%H Peter Steinbach, <a href="/A000664/a000664_8.pdf">Field Guide to Simple Graphs, Volume 4</a>, Part 8 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Eric Swartz, Nicholas J. Werner, <a href="https://arxiv.org/abs/1709.05390">Zero pattern matrix rings, reachable pairs in digraphs, and Sharp's topological invariant tau</a>, arXiv:1709.05390 [math.CO], 2017.

%H Wietske Visser, Koen V. Hindriks and Catholijn M. Jonker, <a href="http://mmi.tudelft.nl/sites/default/files/visser_hindriks_jonker_2012b.pdf">Goal-based Qualitative Preference Systems</a>, 2012.

%H N. L. White, <a href="/A000798/a000798_6.pdf">Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure</a>

%H J. A. Wright, <a href="/A000798/a000798_2.pdf">Letter to N. J. A. Sloane, Nov 21 1970, with four enclosures</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_5.pdf">Two related abstracts, 1970 and 1972</a> [Annotated scanned copies]

%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/Cor#core">Index entries for "core" sequences</a>

%F Related to A001035 by a(n) = Sum Stirling2(n, k)*A001035(k).

%F E.g.f.: A(exp(x) - 1) where A(x) is the e.g.f. for A001035. - _Geoffrey Critzer_, Jul 28 2014

%e From _Gus Wiseman_, Aug 01 2019: (Start)

%e The a(3) = 29 topologies are the following (empty sets not shown):

%e {123} {1}{123} {1}{12}{123} {1}{2}{12}{123} {1}{2}{12}{13}{123}

%e {2}{123} {1}{13}{123} {1}{3}{13}{123} {1}{2}{12}{23}{123}

%e {3}{123} {1}{23}{123} {2}{3}{23}{123} {1}{3}{12}{13}{123}

%e {12}{123} {2}{12}{123} {1}{12}{13}{123} {1}{3}{13}{23}{123}

%e {13}{123} {2}{13}{123} {2}{12}{23}{123} {2}{3}{12}{23}{123}

%e {23}{123} {2}{23}{123} {3}{13}{23}{123} {2}{3}{13}{23}{123}

%e {3}{12}{123}

%e {3}{13}{123} {1}{2}{3}{12}{13}{23}{123}

%e {3}{23}{123}

%e (End)

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

%Y Row sums of A326882.

%Y Cf. A001035 (labeled posets), 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. A102894, A102895, A102897, A306445, A326866, A326876, A326878, A326881.

%K nonn,nice,core,hard

%O 0,3

%A _N. J. A. Sloane_

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

%E a(17)-a(18) are from Brinkmann's and McKay's paper. - _Vladeta Jovovic_, Jun 10 2007

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 14 14:59 EST 2019. Contains 329979 sequences. (Running on oeis4.)