login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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)
56

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

%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 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 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 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 A000798(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

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

%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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 20 17:45 EDT 2018. Contains 304340 sequences. (Running on oeis4.)