login
A369778
Number of inequivalent (as defined below) transitive binary relations on [n].
2
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
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
Row sums of A369776.
Sequence in context: A330471 A121417 A232549 * A284762 A296718 A201862
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jan 31 2024
STATUS
approved