A001035 -id:A001035 - cp's OEIS frontend

A006058 Number of connected labeled T_4-topologies with n points.

1, 1, 3, 16, 145, 2111, 47624, 1626003, 82564031, 6146805142, 662718022355, 102336213875523, 22408881211102698, 6895949927379360277, 2958271314760111914191, 1756322140048351303019576

Offset: 0

N. J. A. Sloane

From Gus Wiseman, Aug 05 2019: (Start)
For n > 0, also the number of topologies covering {1..n} whose nonempty open sets have nonempty intersection. Also the number of topologies covering {1..n} whose nonempty open sets are pairwise intersecting. For example, the a(0) = 1 through a(3) = 16 topologies (empty sets not shown) are:
  {}  {{1}}  {{1,2}}      {{1,2,3}}
             {{1},{1,2}}  {{1},{1,2,3}}
             {{2},{1,2}}  {{2},{1,2,3}}
                          {{3},{1,2,3}}
                          {{1,2},{1,2,3}}
                          {{1,3},{1,2,3}}
                          {{2,3},{1,2,3}}
                          {{1},{1,2},{1,2,3}}
                          {{1},{1,3},{1,2,3}}
                          {{2},{1,2},{1,2,3}}
                          {{2},{2,3},{1,2,3}}
                          {{3},{1,3},{1,2,3}}
                          {{3},{2,3},{1,2,3}}
                          {{1},{1,2},{1,3},{1,2,3}}
                          {{2},{1,2},{2,3},{1,2,3}}
                          {{3},{1,3},{2,3},{1,2,3}}
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Herman Jamke, Table of n, a(n) for n = 0..19
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)

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

Cf. A001930, A003465, A108798, A306445, A326878, A326906.

stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[Select[stableSets[Subsets[Range[n],{1,n}],Intersection[#1,#2]=={}&],Union@@#==Range[n]&&SubsetQ[#,Union[Union@@@Tuples[#,2],Intersection@@@Tuples[#,2]]]&]],{n,0,4}] (* Gus Wiseman, Aug 05 2019 *)
A000798 = Append[Cases[Import["https://oeis.org/A000798/b000798.txt", "Table"], {, }][[All, 2]], 0];
a[n_] := If[n == 0, 1, Sum[ Binomial[n, k] A000798[[k+1]], {k, 0, n-1}]];
a /@ Range[0, Length[A000798]-1] (* Jean-François Alcover, Jan 01 2020 *)

From Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008: (Start)
a(n) = Sum_{k=0..n-1} binomial(n, k)*A000798(k) if n>=1.
E.g.f.: Z4(x) = A(x)*(exp(x)-1) + 1 where A(x) denotes the e.g.f. for A000798. (End)
a(n) = A326909(n) - A000798(n). - Gus Wiseman, Aug 05 2019

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

A001927 Number of connected partially ordered sets with n labeled points.

Original entry on oeis.org

1, 1, 2, 12, 146, 3060, 101642, 5106612, 377403266, 40299722580, 6138497261882, 1320327172853172, 397571105288091506, 166330355795371103700, 96036130723851671469482, 76070282980382554147600692, 82226869197428315925408327266, 120722306604121583767045993825620, 239727397782668638856762574296226842

Offset: 0

N. J. A. Sloane

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

C. M. Bender et al., Combinatorics and field theory, arXiv:quant-ph/0604164, 2006.
G. Brinkmann, B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179 (Table II, up to 18 points)
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]
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
M. Erné and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
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
Index entries for sequences related to posets

Cf. A000112, A001035, A000608, A066303, A342501 (refined by rank).

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

A001035 = {1, 1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579, 122152541250295322862941281269151, 241939392597201176602897820148085023};
max = Length[A001035]-1;
B[x_] = Sum[A001035[[k+1]]*x^k/k!, {k, 0, max}];
A[x_] = 1 + Log[B[x]];
CoefficientList[A[x] + O[x]^(max-1), x]*Range[0, max-2]! (* Jean-François Alcover, Apr 17 2014, updated Aug 30 2018 *)

E.g.f. A(x)=log(B(x)) where B(x) is e.g.f. of A001035.

More terms from Christian G. Bower, Dec 12 2001

a(17)-a(18) using data from A001035 from Alois P. Heinz, Aug 30 2018

A001929 Number of connected topologies on n labeled points.

Original entry on oeis.org

1, 1, 3, 19, 233, 4851, 158175, 7724333, 550898367, 56536880923, 8267519506789, 1709320029453719, 496139872875425839, 200807248677750187825, 112602879608997769049739, 86955243134629606109442219, 91962123875462441868790125305, 132524871920295877733718959290203, 259048612476248175744581063815546423

Offset: 0

N. J. A. Sloane

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

C. M. Bender et al., Combinatorics and Field theory, arXiv:quant-ph/0604164, 2006.
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179, Table IV up to 18 points
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]
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
M. Erné and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
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

Cf. A001928, A001930.

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

A001035 = {1, 1, 3, 19, 219, 4231, 130023, 6129859, 431723379, 44511042511, 6611065248783, 1396281677105899, 414864951055853499, 171850728381587059351, 98484324257128207032183, 77567171020440688353049939, 83480529785490157813844256579, 122152541250295322862941281269151, 241939392597201176602897820148085023};
max = Length[A001035]-1;
B[x_] = Sum[A001035[[k+1]]*x^k/k!, {k, 0, max}];
A[x_] = 1 + Log[B[x]];
A001927 = CoefficientList[ A[x] + O[x]^(max-1), x]*Range[0, max-2]!;
a[n_] := Sum[StirlingS2[n, k] *A001927[[k+1]], {k, 0, n}];
Table[a[n], {n, 0, max -2}] (* Jean-François Alcover, Aug 30 2018, after Vladeta Jovovic *)

a(n) = Sum_{k=0..n} Stirling2(n,k)*A001927(k). - Vladeta Jovovic, Apr 10 2006

More terms from Vladeta Jovovic, Apr 10 2006

a(17)-a(18) using data from A001035 from Alois P. Heinz, Aug 30 2018

A006057 Number of topologies on n labeled points satisfying axioms T_0-T_4.

Original entry on oeis.org

1, 1, 3, 16, 137, 1826, 37777, 1214256, 60075185, 4484316358, 493489876721, 78456654767756, 17735173202222665, 5630684018989523274, 2486496790249207981169, 1515191575312017416011456

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008, Table of n, a(n) for n = 0..19
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
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, International Journal of Combinatorics, Volume 2014 (2014), Article ID 798074, 7 pages.

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

E.g.f.: A04(x)=exp(Z04(x)-1) where Z04(x) denotes the E.g.f. for A006059. - Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

More precise definition from N. J. A. Sloane, Jan 09 2014

A002824 Number of precomplete Post functions.

Original entry on oeis.org

1, 3, 18, 190, 3285, 88851, 3640644, 220674924, 19427552055, 2448107338105, 436330306419678, 108909970814260122, 37752710546082668409, 18044326480066641231855, 11818118910855384843861960, 10549135258779933616014791704, 12772521057179994145518171256587

Offset: 2

N. J. A. Sloane

nonn

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).
E. Ju. Zaharova, V. B. Kudrjavcev, and S. V. Jablonskii, Precomplete classes in k-valued logics. (Russian) Dokl. Akad. Nauk SSSR 186 (1969), 509-512. English translation in Soviet Math. Doklady 10 (No. 3, 1969), 618-622.

Ivo Rosenberg, The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 1-7.
Ivo Rosenberg and N. J. A. Sloane, Correspondence, 1971
E. Ju. Zaharova, V. B. Kudrjavcev, and S. V. Jablonskii, Precomplete classes in k-valued logics. (Russian), Dokl. Akad. Nauk SSSR 186 (1969), 509-512. English translation in Soviet Math. Doklady 10 (No. 3, 1969), 618-622. [Annotated scanned copy]

Cf. A001035.

A001035 = DeleteCases[Import["https://oeis.org/A001035/b001035.txt", "Table"], b_ /; ! MatchQ[b, {_Integer, _Integer}] ][[All, 2]];
a[n_] := Binomial[n, 2] * A001035[[n - 1]];
Table[a[n], {n, 2, Length[A001035] + 1}] (* Jean-François Alcover, May 11 2019 *)

a(n) = binomial(n, 2) * A001035(n - 2). - Sean A. Irvine, Aug 24 2014

More terms from Alois P. Heinz, Jun 02 2017

A121337 Number of idempotent relations on n labeled elements.

Original entry on oeis.org

1, 2, 11, 123, 2360, 73023, 3465357

Offset: 0

Florian Kammüller (flokam(AT)cs.tu-berlin.de), Aug 28 2006

A relation r is idempotent if r ; r = r, where ; denotes sequential composition.
From Geoffrey Critzer, Oct 18 2023 : (Start)
a(n) is also the number of maximal subgroups in the semigroup of binary relations on [n].  See Butler and Markowski link.
A binary relation is idempotent iff it is both dense (A355730) and transitive (A006905).
A binary relation is idempotent iff it is both limit dominating (A366194) and limit dominated (A366722).  See Gregory, Kirkland, and Pullman link.
A binary relation R on [n] is idempotent iff the following biconditional statement holds for all x,y in [n]:  There is a cyclic traverse from x to y in G(R) iff (x,y) is in R.  Here, G(R) is the directed graph with self loops allowed (A002416) corresponding to R.  See Rosenblatt link.
Let Q be a quasi-order (A000798) on [n].  Let D(X) be the relation {(x,x):x is in X}.  Let S be a subset of [n] such that: (i) For all x in S, the class in the equivalence relation Q intersect Q^(-1) containing (x,x) is a singleton and (ii) for all x,y in S, the component containing x is not covered by the component containing y in the condensation of G(Q) .  Here, the condensation of G(Q) is the acyclic digraph (A003024) obtained from G(Q) by replacing every strongly connected component (SCC) by a single vertex and all directed edges from one SCC to another with a single directed edge.  Then a relation is idempotent iff it is of the form Q-D(S).  See Schein link.  (End)

			a(2) = 11 because given a set {a,b} of two elements, of the 2^(2*2) = 16 relations on the set, only 5 are not idempotent. - _Michael Somos_, Jul 28 2013
These 5 relations that are not idempotent are: {(a,b)}, {(b,a)}, {(a,b),(b,a)}, {(a,b),(b,a),(b,b)}, {(a,a),(a,b),(b,a)}. - _Geoffrey Critzer_, Aug 07 2016

F. Kammüller, Interactive Theorem Proving in Software Engineering, Habilitationsschrift, Technische Universitaet Berlin (2006).
Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Decker, 1982.

G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
K. K.-H. Butler and G. Markowsky, The Number of Maximal Subgroups of the Semigroup of Binary Relations, Kyungpook Math. J. Vol 12, June 1972.
D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
F. Kammüller, Counting idempotent relations.
F. Kammüller and J. W. Sanders, Idempotent relations in Isabelle/HOL, International Colloquium on Theoretical Aspects of Computing, ICTAC'04. Volume 3407 of Lecture Notes in Computer Science, Springer-Verlag (2005).
G. Pfeiffer, Counting transitive relations, J. Integer Sequences, Volume 7, 2004, #3.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.

Cf. A000798 (labeled quasi-orders (or topologies)), A001930 (unlabeled quasi-orders), A001035 (labeled partial orders), A000112 (unlabeled partial orders), A002416, A003024, A366722, A366194, A355730, A006905.

Row sums of A360984.

Prepend[Table[Length[Select[Tuples[Tuples[{0, 1}, n], n], (MatrixPower[#, 2] /. x_ /; x > 0 -> 1) == # &]], {n, 1, 4}], 1] (* Geoffrey Critzer, Aug 07 2016 *)

Offset corrected by James Mitchell, Jul 28 2013

a(1) corrected by Philippe Beaudoin, Aug 11 2015

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Original entry on oeis.org

2, 1, 1, 5, 76, 5993, 7689745, 2414465044600, 56130437141763247212112, 286386577668298408602599478477358234902247

Offset: 0

Patrick De Causmaecker, Jul 25 2014

This is the number of antichain covers such that the induced partition contains only singletons. The induced partition of {{1,2},{2,3},{1,3},{3,4}} is {{1},{2},{3},{4}}, while the induced partition of {{1,2,3},{2,3,4}} is {{1},{2,3},{4}}.
This sequence is related to A006126. See 1st formula.
The sequence is also related to Dedekind numbers through Stirling numbers of the second kind. See 2nd formula.
Sets of subsets of the described type are said to be T_0. - Gus Wiseman, Aug 14 2019

			For n = 0, a(0) = 2 by the antisets {}, {{}}.
For n = 1, a(1) = 1 by the antiset {{1}}.
For n = 2, a(2) = 1 by the antiset {{1},{2}}.
For n = 3, a(3) = 5 by the antisets {{1},{2},{3}}, {{1,2},{1,3}}, {{1,2},{2,3}}, {{1,3},{2,3}}, {{1,2},{1,3},{2,3}}.

Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.

Cf. A000372 (Dedekind numbers), A006126 (Number of antichain covers of a labeled n-set).
Sequences counting and ranking T_0 structures:
  A000112 (unlabeled topologies),
  A001035 (topologies),
  A059201 (covering set-systems),
  A245567 (antichain covers),
  A309615 (covering set-systems closed under intersection),
  A316978 (factorizations),
  A319559 (unlabeled set-systems by weight),
  A319564 (integer partitions),
  A319637 (unlabeled covering set-systems),
  A326939 (covering sets of subsets),
  A326940 (set-systems),
  A326941 (sets of subsets),
  A326943 (covering sets of subsets closed under intersection),
  A326944 (covering sets of subsets with {} and closed under intersection),
  A326945 (sets of subsets closed under intersection),
  A326946 (unlabeled set-systems),
  A326947 (BII-numbers of set-systems),
  A326948 (connected set-systems),
  A326949 (unlabeled sets of subsets),
  A326950 (antichains),
  A326959 (set-systems closed under intersection),
  A327013 (unlabeled covering set-systems closed under intersection),
  A327016 (BII-numbers of topologies).

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
Table[Length[Select[Subsets[Subsets[Range[n]]],Union@@#==Range[n]&&stableQ[#,SubsetQ]&&UnsameQ@@dual[#]&]],{n,0,3}] (* Gus Wiseman, Aug 14 2019 *)

A000372(n) = Sum_{k=0..n} S(n+1,k+1)*a(k).
a(n) = A006126(n) - Sum_{k=1..n-1} S(n,k)*a(k).
Were n > 0 and S(n,k) is the number of ways to partition a set of n elements into k nonempty subsets.
Inverse binomial transform of A326950, if we assume a(0) = 1. - Gus Wiseman, Aug 14 2019

Definition corrected by Patrick De Causmaecker, Oct 10 2014

a(9), based on A000372, from Patrick De Causmaecker, Jun 01 2023

A006056 Number of topologies on n labeled points satisfying the T_4 axiom.

Original entry on oeis.org

1, 1, 4, 26, 255, 3642, 75606, 2316169, 106289210, 7321773414, 748425136289, 111576624613588, 23864968806932886, 7225895692327786931, 3064182503223082011556, 1803904252801640389374494, 1463405916763710662849541695, 1625522872429294851288338156654

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Herman Jamke, Table of n, a(n) for n = 0..19
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)

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

E.g.f.: A4(X) = exp(Z4(X)-1) where Z4(x) denotes the e.g.f. for A006058. - Herman Jamke, Mar 02 2008

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

More precise definition from N. J. A. Sloane, Jan 09 2014

A006059 Number of connected labeled T_0-T_4-topologies with n points.

Original entry on oeis.org

1, 1, 2, 9, 76, 1095, 25386, 910161, 49038872, 3885510411, 445110425110, 72721717736613, 16755380125270788, 5393244363726095487, 2405910197342218830914, 1477264863856923105482745, 1241074736327051013648799024, 1419169006353332682835352361843

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Herman Jamke, Table of n, a(n) for n = 0..19
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)

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

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
a[n_] := If[n == 0, 1, n A001035[[n]]];
a /@ Range[0, Length[A001035]] (* Jean-François Alcover, Dec 30 2019 *)

a(n) = n*A001035(n-1) for n>=1. - Herman Jamke (hermanjamke(AT)fastmail.fm), Mar 02 2008

More terms from Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2001

A006455 Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x

Original entry on oeis.org

1, 1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684

Offset: 0

N. J. A. Sloane

Also known as naturally labeled posets. - David Bevan, Nov 16 2023
Also the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2.
The asymptotic values derived by Brightwell et al. are relevant only for extremely large values of n. The average number of linear extensions (topological sorts) of a random partial order on {1,...,n} is n! S_n / N_n, where S_n is this sequence and N_n is sequence A001035

			a(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.

N. B. Hindman, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. P. Avann, The lattice of natural partial orders, Aequationes Mathematicae 8 (1972), 95-102.
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
Graham Brightwell, Hans Jürgen Prömel and Angelika Steger, The average number of linear extensions of a partial order, Journal of Combinatorial Theory A73 (1996), 193-206.
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]
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
L. H. Harper, The Range of a Steiner Operation, arXiv preprint arXiv:1608.07747 [math.CO], 2016.
N. Hindman and N. J. A. Sloane, Correspondence, 1981-1991
Florent Hivert and Nicolas M. Thiéry, Controlling the C3 Super Class Linearization Algorithm for Large Hierarchies of Classes, Order (2022).
Adam King, A. Laubmeier, K. Orans, and A. Godbole, Universal and Overlap Cycles for Posets, Words, and Juggling Patterns, arXiv preprint arXiv:1405.5938 [math.CO], 2014.
D. E. Knuth, POSETS, program for n = 10, 11, 12.
J.-G. Luque, L. Mignot and F. Nicart, Some Combinatorial Operators in Language Theory, arXiv preprint arXiv:1205.3371 [cs.FL], 2012. - _N. J. A. Sloane_, Oct 22 2012
Index entries for sequences related to posets

Cf. A000112, A001035, A323502.

E.g.f.: exp(S(x)-1) where S(x)is the e.g.f. for A323502. - Ludovic Schwob, Mar 29 2024

Additional comments and more terms from Don Knuth, Dec 03 2001

cp's OEIS Frontend

A006058 Number of connected labeled T_4-topologies with n points.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001927 Number of connected partially ordered sets with n labeled points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A001929 Number of connected topologies on n labeled points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A006057 Number of topologies on n labeled points satisfying axioms T_0-T_4.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A002824 Number of precomplete Post functions.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A121337 Number of idempotent relations on n labeled elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A245567 Number of antichain covers of a labeled n-set such that for every two distinct elements in the n-set, there is a set in the antichain cover containing one of the elements but not the other.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A006056 Number of topologies on n labeled points satisfying the T_4 axiom.