This site is supported by donations to The OEIS Foundation.



(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)
1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021, 207881393656668953041, 115617051977054267807460, 88736269118586244492485121, 93411113411710039565210494095, 134137950093337880672321868725846, 261492535743634374805066126901117203 (list; graph; refs; listen; history; text; internal format)



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


Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.

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.

S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.

Tyler Clark and Tom Richmond, The Number of Convex Topologies on a Finite Totally Ordered Set, 2013, to appear in Involve; http://people.wku.edu/tom.richmond/Papers/CountConvexTopsFTOsets.pdf

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

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

M. Erne', Struktur- und Anzahlformeln fuer Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.

M. Erne' 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.

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.

J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.

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.

M. Kolli, On the cardinality of the T_0-topologies on a finite set, Preprint, 2014.

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) - From N. J. A. Sloane, Jun 05 2012

M. Rayburn, On the Borel fields of a finite set, Proc. Amer. Math.. Soc., 19 (1968), 885-889.

A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198.

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.


Table of n, a(n) for n=0..18.

Gunnar Brinkmann and Brendan D. McKay, Posets on up to 16 points.

G. Brinkmann,  B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179 (Table IV).

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

L. Foissy, C. Malvenuto, F. Patras, B_infinity-algebras, their enveloping algebras, and finite spaces, arXiv preprint arXiv:1403.7488, 2014

L. Foissy and C. Malvenuto, The Hopf algebra of finite topologies and T-partitions, arXiv preprint arXiv:1407.0476, 2014

S. Giraudo, J.-G. Luque, L. Mignot and F. Nicart, Operads, quasiorders and regular languages, arXiv preprint arXiv:1401.2010, 2014

Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers

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

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

D. Rusin, More info and references

N. J. A. Sloane, Classic Sequences

Wietske Visser, Koen V. Hindriks and Catholijn M. Jonker, Goal-based Qualitative Preference Systems,  2012. - From N. J. A. Sloane, Oct 07 2012

Index entries for "core" sequences


Related to A001035 by A000798(n) = Sum 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


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

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

Sequence in context: A137646 A231498 A168602 * A135485 A210526 A221079

Adjacent sequences:  A000795 A000796 A000797 * A000799 A000800 A000801




N. J. A. Sloane.


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



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

Content is available under The OEIS End-User License Agreement .

Last modified July 29 21:54 EDT 2015. Contains 260114 sequences.