cp's OEIS Frontend

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

%I A369778 #18 Feb 03 2024 10:13:28
%S A369778 1,2,9,69,838,15673,446723,19293060,1251685959,120386313553,
%T A369778 16900121126060,3411142115103803,977085613480027515,
%U A369778 392874276568326733742,219743920204264577507581,169664195991510052549565897,179646979835553234783655867894,259379781267410563698300438118605,508142540645401577520522108019282903
%N A369778 Number of inequivalent (as defined below) transitive binary relations on [n].
%C A369778 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.
%C A369778 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.
%C A369778 Conjecture:  lim_{n->oo} a(n)/A001035(n) = 2.
%H A369778 E. Norris, <a href="https://www.researchgate.net/publication/225547994_The_structure_of_an_idempotent_relation">The structure of an idempotent relation</a>, Semigroup Forum, Vol 18 (1979), 319-329.
%F A369778 E.g.f.: p(exp(x) - 1)*p(x) where p(x) is the e.g.f. for A001035.
%t A369778 nn = 16; posets = Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
%t A369778    Length@# == 2 &][[All, 2]];p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]];
%t A369778 Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[   x] - 1]*p[ x], {x, 0, nn}], x]
%Y A369778 Cf. A000798, A001035, A006905, A369799,
%Y A369778 Row sums of A369776.
%K A369778 nonn
%O A369778 0,2
%A A369778 _Geoffrey Critzer_, Jan 31 2024