cp's OEIS Frontend

A369776 Triangular array read by rows. T(n,k) is the number of inequivalent (as defined below) transitive binary relations R on [n] such that |domain(R intersect R^(-1))| = k, n>=0, 0<=k<=n.

%I A369776 #20 Feb 03 2024 10:14:35
%S A369776 1,1,1,3,2,4,19,9,12,29,219,76,72,116,355,4231,1095,760,870,1775,6942,
%T A369776 130023,25386,13140,11020,15975,41652,209527,6129859,910161,355404,
%U A369776 222285,236075,437346,1466689,9535241,431723379,49038872,14562576,6871144,5442150,7386288,17600268,76281928,642779354
%N A369776 Triangular array read by rows.  T(n,k) is the number of inequivalent (as defined below) transitive binary relations R on [n] such that |domain(R intersect R^(-1))| = k, n>=0, 0<=k<=n.
%C A369776 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).  The relation q(R) union s(R) may be taken as its class representative.  See Norris link.
%H A369776 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 A369776 E.g.f.: p(exp(y*x) - 1)*p(x) where p(x) is the e.g.f. for A001035.
%e A369776 Triangle begins
%e A369776     1;
%e A369776     1,    1;
%e A369776     3,    2,   4;
%e A369776    19,    9,  12,  29;
%e A369776   219,   76,  72, 116,  355;
%e A369776  4231, 1095, 760, 870, 1775, 6942;
%e A369776  ...
%t A369776 nn = 8; posets = Select[Import["https://oeis.org/A001035/b001035.txt", "Table"],
%t A369776    Length@# == 2 &][[All, 2]];p[x_] := Total[posets Table[x^i/i!, {i, 0, 18}]];
%t A369776 Map[Select[#, # > 0 &] &,Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[ y  x] - 1]*p[ x], {x, 0, nn}], {x, y}]] // Grid
%Y A369776 Cf. A001035 (column k=0), A000798 (main diagonal), A006059 (column k=1), A369778 (row sums), A006905, A369799.
%K A369776 nonn,tabl
%O A369776 0,4
%A A369776 _Geoffrey Critzer_, Jan 31 2024