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,2

Comments

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.

Links

Table of n, a(n) for n=0..18.

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

Formula

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

Mathematica

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]

Crossrefs

Cf. A000798, A001035, A006905, A369799,

Row sums of A369776.

Sequence in context: A330471 A121417 A232549 * A284762 A296718 A201862

Adjacent sequences: A369775 A369776 A369777 * A369779 A369780 A369781

Keyword

nonn

Author

Geoffrey Critzer, Jan 31 2024

Status

approved