A369776 -id:A369776 - cp's OEIS frontend

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula