|
|
A000798
|
|
Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.
(Formerly M3631 N1476)
|
|
83
|
|
|
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)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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
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)
|
|
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
|
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]
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. <hal-00967351v2>.
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.)
|
|
FORMULA
|
a(n) = Sum_{k=0..n} Stirling2(n, k)*A001035(k).
It is known that log_2(a(n)) ~ n^2/4. - Tian Vlasic, Feb 23 2022
|
|
EXAMPLE
|
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)
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice,core,hard
|
|
AUTHOR
|
|
|
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
|
|
STATUS
|
approved
|
|
|
|