A001035 -id:A001035 - cp's OEIS frontend

A245731 Number of connected labeled transitive relations on an n-set.

1, 2, 9, 109, 2647, 110481, 7291543, 726434549, 106312974249, 22465350835849, 6771847676632679, 2883916106465622053, 1720792953946798909927, 1427968172285571102335605, 1637002867699829205840095585, 2577011453377960519672777065693, 5541005747990556022043234479371823, 16195114271558690956785525865003941945, 64068293759315414337050896928055465961863

Offset: 0

Geoffrey Critzer, Jul 30 2014

nonn

			a(2) = 9. There are 13 transitive relations on the set {1,2}. Four of these are not connected: {}, {(1,1)}, {(2,2)}, {(1,1),(2,2)}. 13-4=9.

Cf. A001035, A006905.

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

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

A327016 BII-numbers of finite T_0 topologies without their empty set.

Original entry on oeis.org

0, 1, 2, 5, 6, 7, 8, 17, 24, 25, 34, 40, 42, 69, 70, 71, 81, 85, 87, 88, 89, 93, 98, 102, 103, 104, 106, 110, 120, 121, 122, 127, 128, 257, 384, 385, 514, 640, 642, 1029, 1030, 1031, 1281, 1285, 1287, 1408, 1409, 1413, 1538, 1542, 1543, 1664, 1666, 1670, 1920

Offset: 1

Gus Wiseman, Aug 14 2019

nonn

A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.

			The sequence of all finite T_0 topologies without their empty set together with their BII-numbers begins:
   0: {}
   1: {{1}}
   2: {{2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   7: {{1},{2},{1,2}}
   8: {{3}}
  17: {{1},{1,3}}
  24: {{3},{1,3}}
  25: {{1},{3},{1,3}}
  34: {{2},{2,3}}
  40: {{3},{2,3}}
  42: {{2},{3},{2,3}}
  69: {{1},{1,2},{1,2,3}}
  70: {{2},{1,2},{1,2,3}}
  71: {{1},{2},{1,2},{1,2,3}}
  81: {{1},{1,3},{1,2,3}}
  85: {{1},{1,2},{1,3},{1,2,3}}
  87: {{1},{2},{1,2},{1,3},{1,2,3}}
  88: {{3},{1,3},{1,2,3}}

Gus Wiseman, The first 100 finite T_0 topologies, represented as posets.

T_0 topologies are A001035, with unlabeled version A000112.
BII-numbers of topologies without their empty set are A326876.
BII-numbers of T_0 set-systems are A326947.
Cf. A001930, A048793, A306445, A316978, A319564, A326031, A326872, A326875, A326939, A326941, A326959.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,1000],UnsameQ@@dual[bpe/@bpe[#]]&&SubsetQ[bpe/@bpe[#],Union[Union@@@Tuples[bpe/@bpe[#],2],DeleteCases[Intersection@@@Tuples[bpe/@bpe[#],2],{}]]]&]

A334253 Number of strict closure operators on a set of n elements which satisfy the T_0 separation axiom.

Original entry on oeis.org

1, 1, 3, 35, 2039, 1352390, 75945052607, 14087646108883940225

Offset: 0

Joshua Moerman, Apr 20 2020

The T_0 axiom states that the closure of {x} and {y} are different for distinct x and y.

A closure operator is strict if the empty set is closed.

			The a(0) = 1 through a(2) = 3 set-systems of closed sets:
{{}}  {{1},{}}  {{1,2},{1},{}}
                {{1,2},{2},{}}
                {{1,2},{1},{2},{}}

R. S. R. Myers, J. Adámek, S. Milius, and H. Urbat, Coalgebraic constructions of canonical nondeterministic automata, Theoretical Computer Science, 604 (2015), 81-101.
B. Venkateswarlu and U. M. Swamy, T_0-Closure Operators and Pre-Orders, Lobachevskii Journal of Mathematics, 39 (2018), 1446-1452.

The number of all strict closure operators is given in A102894.
For all T0 closure operators, see A334252.
For strict T1 closure operators, see A334255.
A strict closure operator which preserves unions is called topological, see A001035.
Cf. A326943, A326944, A326945.

a(n) = Sum_{k=0..n} Stirling1(n,k) * A102894(k). - Andrew Howroyd, Apr 20 2020

a(6)-a(7) from Andrew Howroyd, Apr 20 2020

A352761 Number of partial order relations on [n] such that 1 and 2 are in the same connected component.

Original entry on oeis.org

2, 14, 176, 3644, 117860, 5755964, 414823916, 43390462724, 6502296995300, 1380924739533644, 411744185101611356, 170949139294419110804, 98118349844314838731220, 77360523694460582654188124, 83319557470828626639253920716, 121980734453060653381753104078884, 241689591664023311258411470178766020

Offset: 2

Geoffrey Critzer, Jul 05 2022

nonn

Cf. A001035, A352399.

nn = 16; A[x_] := Total[Cases[Import["https://oeis.org/A001035/b001035.txt",
      "Table"], {, }][[All, 2]]*Table[x^(i - 1)/(i - 1)!, {i, 1, 19}]];
Range[0, nn]! CoefficientList[ Series[D[D[Log[A[x]], x], x] A[x], {x, 0, nn}], x]

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

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 7, 6, 6, 0, 97, 62, 36, 24, 0, 2251, 1110, 510, 240, 120, 0, 80821, 30902, 11340, 4440, 1800, 720, 0, 4305127, 1273566, 369726, 119280, 42000, 15120, 5040, 0, 332273257, 75831422, 17192196, 4476024, 1335600, 433440, 141120, 40320

Offset: 0

Geoffrey Critzer, Jul 08 2022

			  1;
  0,    1;
  0,    1,    2;
  0,    7,    6,   6;
  0,   97,   62,  36,  24;
  0, 2251, 1110, 510, 240, 120;
  ...

Cf. A046908 (column k=1), A001035 (row sums), A000142 (main diagonal).

nn = 9; A[x_] := Total[Cases[Import["https://oeis.org/A001035/b001035.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}]

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

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.

cp's OEIS Frontend

A245731 Number of connected labeled transitive relations on an n-set.

Views

Author

Keywords

Examples

Crossrefs

Formula

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

A327016 BII-numbers of finite T_0 topologies without their empty set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A334253 Number of strict closure operators on a set of n elements which satisfy the T_0 separation axiom.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A352761 Number of partial order relations on [n] such that 1 and 2 are in the same connected component.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Examples

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