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
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Jan 31 2024
STATUS
approved