A000798 -id:A000798 - cp's OEIS frontend

A122836 Number of topologies on n labeled elements in which at least one element belongs to some pair of noncomparable members of the topology.

0, 0, 0, 10, 243, 6131, 202503, 9464302, 641960602, 63249658532, 8976900501699, 1816843604787333, 519355528928422629, 207881392866381430470, 115617051961092253351796, 88736269118240819706018342, 93411113411702066083187522063, 134137950093337685116171325021995, 261492535743634369726764132015849219

Offset: 0

Nathan K. McGregor (mcgregnk(AT)ese.wustl.edu), Sep 15 2006

See comments in A122835.

J. Munkres, Topology, Prentice Hall, (2000), p. 76.

a(n) = A000798(n) - A122835(n).

A000798 = Cases[Import["https://oeis.org/A000798/b000798.txt", "Table"], {, }][[All, 2]];
a122835[n_] := (3/4)*(PolyLog[-n, 1/2] + Boole[n == 0]) - 1/2;
a[n_] := A000798[[n + 1]] - a122835[n];
a /@ Range[0, 18] (* Jean-François Alcover, Jan 01 2020, after Michael Somos in A122835 *)

a(13) corrected and a(16)-a(18) by Jean-François Alcover, Jan 01 2020

A245767 Triangular array read by rows: T(n,k) is the number of transitive relations on {1,2,...,n} that have exactly k reflexive points, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 6, 4, 19, 57, 66, 29, 219, 876, 1428, 1116, 355, 4231, 21155, 44500, 49070, 28405, 6942, 130023, 780138, 2013810, 2858700, 2354415, 1068576, 209527, 6129859, 42909013, 131457522, 228345565, 242894155, 158322528, 58628647, 9535241

Offset: 0

Geoffrey Critzer, Jul 31 2014

Row sums give A006905.
Column k=0 is A001035.
T(n,n) = A000798(n).

			T(2,1) = 6 because we have: {(1,1)}, {(2,2)}, {(1,1),(1,2)}, {(1,1),(2,1)}, {(2,2),(1,2)}, {(2,2),(2,1)}.
Triangle T(n,k) begins:
       1;
       1,      1;
       3,      6,       4;
      19,     57,      66,      29;
     219,    876,    1428,    1116,     355;
    4231,  21155,   44500,   49070,   28405,    6942;
  130023, 780138, 2013810, 2858700, 2354415, 1068576, 209527;
  ...

Alois P. Heinz, Rows n = 0..18, flattened

Cf. A000798, A001035, A006905.

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
lg = Length[A001035];
A[x_] = Sum[A001035[[n+1]] x^n/n!, {n, 0, lg-1}];
CoefficientList[#, y]& /@ (CoefficientList[A[x + Exp[y*x]-1] + O[x]^lg, x]* Range[0, lg-1]!) // Flatten (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(x + exp(y*x) - 1) where A(x) is the e.g.f. for A001035.

A247231 Triangular array read by rows: T(n,k) is the number of ways to partition an n-set into exactly k blocks and then partially order the blocks, n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 3, 1, 9, 19, 1, 21, 114, 219, 1, 45, 475, 2190, 4231, 1, 93, 1710, 14235, 63465, 130023, 1, 189, 5719, 76650, 592340, 2730483, 6129859, 1, 381, 18354, 372519, 4442550, 34586118, 171636052, 431723379, 1, 765, 57475, 1701630, 29409681, 344040858, 2831994858, 15542041644, 44511042511

Offset: 1

Geoffrey Critzer, Nov 27 2014

T(n,k) is also the number of topologies U on an n-set such that a minimal basis for U contains exactly k sets. - Geoffrey Critzer, Dec 26 2016

T(n,k) is also the number of transitive, reflexive Boolean relation matrices on [n] that have exactly k strongly connected components. - Geoffrey Critzer, Feb 27 2023

			Triangle T(n,k) begins:
  1;
  1,   3;
  1,   9,   19;
  1,  21,  114,   219;
  1,  45,  475,  2190,   4231;
  1,  93, 1710, 14235,  63465,  130023;
  1, 189, 5719, 76650, 592340, 2730483, 6129859;
  ...

Alois P. Heinz, Rows n = 1..18

Row sums gives A000798, n >= 1.
Leading diagonal gives A001035, n >= 1.
Apparently column 2 gives the terms > 1 of A068156.

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
lg = Length[A001035];
A[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, lg - 1}];
Rest[CoefficientList[#, y]]& /@ (CoefficientList[A[y*(Exp[x] - 1)] + O[x]^lg, x]*Range[0, lg - 1]!) // Flatten (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(y*(exp(x) - 1)) where A(x) is the e.g.f. for A001035.

A280192 Triangle read by rows: T(n,k) = number of topologies on an n-set X such that there are exactly k elements in X that are topologically distinguishable, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 1, 0, 3, 1, 9, 0, 19, 10, 12, 114, 0, 219, 31, 300, 190, 2190, 0, 4231, 361, 1158, 10140, 4380, 63465, 0, 130023, 2164, 26341, 46389, 451920, 148085, 2730483, 0, 6129859, 32663, 192496, 1930852, 2381624, 27601000, 7281288, 171636052, 0, 431723379

Offset: 0

Geoffrey Critzer, Dec 28 2016

T(n,0) = A280202(n) is the number of topologies on an n-set X such that for all x in X there exists a y in X such that x and y have exactly the same neighborhoods.

Equivalently, T(n,k) is the number of labeled quasi-orders R on [n] with exactly k singletons in the equivalence relation R intersect R^(-1), cf. Schein link. - Geoffrey Critzer, Apr 18 2023

			Triangle begins:
     1;
     0,     1;
     1,     0,     3;
     1,     9,     0,     19;
    10,    12,   114,      0,    219;
    31,   300,   190,   2190,      0,    4231;
   361,  1158, 10140,   4380,  63465,       0, 130023;
  2164, 26341, 46389, 451920, 148085, 2730483,      0, 6129859;
  ...

Alois P. Heinz, Rows n = 0..18, flattened
B. M. Schein, A construction for idempotent binary relations, Proc. Japan Acad., Vol. 46, No. 3 (1970), pp. 246-247.
Wikipedia, Topological indistinguishability.

Right border gives A001035.
Row sums give A000798.
Column k=0 gives A280202.
Cf. A006905.

A001035 = Cases[Import["https://oeis.org/A001035/b001035.txt", "Table"], {, }][[All, 2]];
lg = Length[A001035];
A[x_] = Sum[A001035[[n + 1]] x^n/n!, {n, 0, lg - 1}];
CoefficientList[#, y]& /@ (CoefficientList[A[Exp[x] - 1 - x + y*x] + O[x]^lg, x]*Range[0, lg - 1]!) // Flatten (* Jean-François Alcover, Jan 01 2020 *)

E.g.f.: A(exp(x) - 1 - x + y*x) where A(x) is the e.g.f. for A001035.

Sum_{k=0..n} T(n,k)*2^k = A006905(n). - Geoffrey Critzer, Apr 18 2023

A335987 Triangular array read by rows: T(n,k) is the number of labeled quasi-orders on [n] that are composed of exactly k irreducible components n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 0, 2, 2, 0, 11, 12, 6, 0, 147, 112, 72, 24, 0, 3412, 1910, 1020, 480, 120, 0, 121553, 52184, 21870, 9600, 3600, 720, 0, 6353629, 2101540, 693672, 254520, 96600, 30240, 5040, 0, 476850636, 120988214, 31163496, 9289728, 3116400, 1048320, 282240, 40320

Offset: 0

Geoffrey Critzer, Jul 10 2022

			  1;
  0,    1;
  0,    2,    2;
  0,   11,   12,    6;
  0,  147,  112,   72,  24;
  0, 3412, 1910, 1020, 480, 120;
  ...

Alois P. Heinz, Rows n = 0..18, flattened

Cf. A000798 (row sums), A046912 (column k=1), A000142 (main diagonal), A354615.

nn = 9; A[x_] := Total[Cases[Import["https://oeis.org/A000798/b000798.txt",
      "Table"], {, }][[All, 2]]*Table[x^(i - 1)/(i - 1)!, {i, 1, 19}]];
Table[Take[(Range[0, nn]! CoefficientList[Series[1/(1 - y (1 - 1/A[x])), {x, 0, nn}], {x, y}])[[i]],  i], {i, 1, nn}] // Grid

E.g.f.: 1/(1 - y*(1 - 1/A(x))) where A(x) is the e.g.f. for A000798.

A369776 Triangular array read by rows. T(n,k) is the number of inequivalent (as defined below) transitive binary relations R on [n] such that |domain(R intersect R^(-1))| = k, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 2, 4, 19, 9, 12, 29, 219, 76, 72, 116, 355, 4231, 1095, 760, 870, 1775, 6942, 130023, 25386, 13140, 11020, 15975, 41652, 209527, 6129859, 910161, 355404, 222285, 236075, 437346, 1466689, 9535241, 431723379, 49038872, 14562576, 6871144, 5442150, 7386288, 17600268, 76281928, 642779354

Offset: 0

Geoffrey Critzer, Jan 31 2024

For a transitive relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E. Let q(R) = R intersect E X E and let s(R) = R intersect F X F. Let ~ be the equivalence relation on the set of transitive binary relations on [n] defined by: R_1 ~ R_2 iff q(R_1) = q(R_2) and s(R_1) = s(R_2). Here, two transitive relations are inequivalent if they are in distinct equivalence classes under ~. q(R) is a quasi-order (A000798) and s(R) is a strict partial order (A001035). The relation q(R) union s(R) may be taken as its class representative. See Norris link.

			Triangle begins
    1;
    1,    1;
    3,    2,   4;
   19,    9,  12,  29;
  219,   76,  72, 116,  355;
 4231, 1095, 760, 870, 1775, 6942;
 ...

E. Norris, The structure of an idempotent relation, Semigroup Forum, Vol 18 (1979), 319-329.

Cf. A001035 (column k=0), A000798 (main diagonal), A006059 (column k=1), A369778 (row sums), A006905, A369799.

nn = 8; posets = Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
   Length@# == 2 &][[All, 2]];p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]];
Map[Select[#, # > 0 &] &,Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[ y  x] - 1]*p[ x], {x, 0, nn}], {x, y}]] // Grid

E.g.f.: p(exp(y*x) - 1)*p(x) where p(x) is the e.g.f. for A001035.

A369778 Number of inequivalent (as defined below) transitive binary relations on [n].

Original entry on oeis.org

1, 2, 9, 69, 838, 15673, 446723, 19293060, 1251685959, 120386313553, 16900121126060, 3411142115103803, 977085613480027515, 392874276568326733742, 219743920204264577507581, 169664195991510052549565897, 179646979835553234783655867894, 259379781267410563698300438118605, 508142540645401577520522108019282903

Offset: 0

Geoffrey Critzer, Jan 31 2024

nonn

For a transitive relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E.  Let q(R) = R intersect E X E and let s(R) = R intersect F X F.  Let ~ be the equivalence relation on the set of transitive binary relations on [n] defined by: R_1 ~ R_2 iff q(R_1) = q(R_2) and s(R_1) = s(R_2).  Here, two transitive relations are inequivalent if they are in distinct equivalence classes under ~.  q(R) is a quasi-order (A000798) and s(R) is a strict partial order (A001035). See Norris link.
Equivalently, with E,F as defined above, a(n) is the number of transitive relations R on [n] such that if (x,y) is in R then x and y are both in E or x and y are both in F.
Conjecture:  lim_{n->oo} a(n)/A001035(n) = 2.

E. Norris, The structure of an idempotent relation, Semigroup Forum, Vol 18 (1979), 319-329.

Cf. A000798, A001035, A006905, A369799,

Row sums of A369776.

nn = 16; posets = Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
   Length@# == 2 &][[All, 2]];p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]];
Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[   x] - 1]*p[ x], {x, 0, nn}], x]

E.g.f.: p(exp(x) - 1)*p(x) where p(x) is the e.g.f. for A001035.

A369799 Number of binary relations R on [n] such that q(R) is a quasi-order and s(R) is a strict partial order (where q(R) and s(R) are defined below).

Original entry on oeis.org

1, 2, 13, 237, 11590, 1431913, 424559959, 292150780260, 456213083587511, 1589279411184268465, 12188163803127032036308, 203538148644721100472292979, 7336995548182992341725851094195, 566597426371900580541745092349604750, 93154354372753215966288131247384428212545, 32423220989898980232206367503220063835343283713

Offset: 0

Geoffrey Critzer, Feb 01 2024

nonn

For a relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E. Then q(R) := R intersect E X E and let s(R) := R intersect F X F.

E. Norris, The structure of an idempotent relation, Semigroup Forum, Vol 18 (1979), 319-329.

Cf. A369778, A369776, A001035, A000798.

nn = 18; posets =Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
   Length@# == 2 &][[All, 2]]; p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]]; Map[Total, (Map[Select[#, # > 0 &] &,Table[n!, {n, 0, nn}] CoefficientList[
      Series[ p[Exp[ y  x] - 1]*p[ x], {x, 0, nn}], {x, y}]])*
  Table[Table[3^(k (n - k)), {k, 0, n}], {n, 0, nn}]]

a(n) = Sum_{k=0..n} A369776(n,k) * 3^(k*(n-k)).

A046904 Number of isomorphism classes of posets with n points with property that there is no nonsingelton proper subset T for which x not in T implies xT or x incomparable with every element of T.

Original entry on oeis.org

1, 1, 0, 0, 1, 4, 28, 234

Offset: 0

John A. Wright

nonn

J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.

A subset of the posets enumerated in A003431. Cf. A046905.

A046905 Posets with n points with property that there is no nonsingelton proper subset T for which x not in T implies xT or x incomparable with every element of T.

Original entry on oeis.org

1, 1, 0, 0, 24, 360, 17400, 1066800

Offset: 0

John A. Wright

nonn

J. A. Wright, There are 718 6-point topologies, quasi-orderings and transgraphs, Notices Amer. Math. Soc., 17 (1970), p. 646, Abstract #70T-A106.

A subset of the posets enumerated in A003431. Cf. A046904.

cp's OEIS Frontend

A122836 Number of topologies on n labeled elements in which at least one element belongs to some pair of noncomparable members of the topology.

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

Extensions

A245767 Triangular array read by rows: T(n,k) is the number of transitive relations on {1,2,...,n} that have exactly k reflexive points, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A247231 Triangular array read by rows: T(n,k) is the number of ways to partition an n-set into exactly k blocks and then partially order the blocks, n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A280192 Triangle read by rows: T(n,k) = number of topologies on an n-set X such that there are exactly k elements in X that are topologically distinguishable, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A335987 Triangular array read by rows: T(n,k) is the number of labeled quasi-orders on [n] that are composed of exactly k irreducible components n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A369776 Triangular array read by rows. T(n,k) is the number of inequivalent (as defined below) transitive binary relations R on [n] such that |domain(R intersect R^(-1))| = k, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A369778 Number of inequivalent (as defined below) transitive binary relations on [n].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A369799 Number of binary relations R on [n] such that q(R) is a quasi-order and s(R) is a strict partial order (where q(R) and s(R) are defined below).

Views

Author

Keywords

Comments