A369778 -id:A369778 - cp's OEIS frontend

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.

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.

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

cp's OEIS Frontend

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