login
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.
2
1, 1, 1, 3, 2, 4, 19, 9, 12, 29, 219, 76, 72, 116, 355, 4231, 1095, 760, 870, 1775, 6942, 130023, 25386, 13140, 11020, 15975, 41652, 209527, 6129859, 910161, 355404, 222285, 236075, 437346, 1466689, 9535241, 431723379, 49038872, 14562576, 6871144, 5442150, 7386288, 17600268, 76281928, 642779354
OFFSET
0,4
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). The relation q(R) union s(R) may be taken as its class representative. See Norris link.
LINKS
E. Norris, The structure of an idempotent relation, Semigroup Forum, Vol 18 (1979), 319-329.
FORMULA
E.g.f.: p(exp(y*x) - 1)*p(x) where p(x) is the e.g.f. for A001035.
EXAMPLE
Triangle begins
1;
1, 1;
3, 2, 4;
19, 9, 12, 29;
219, 76, 72, 116, 355;
4231, 1095, 760, 870, 1775, 6942;
...
MATHEMATICA
nn = 8; 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}]];
Map[Select[#, # > 0 &] &, Table[n!, {n, 0, nn}] CoefficientList[Series[ p[Exp[ y x] - 1]*p[ x], {x, 0, nn}], {x, y}]] // Grid
CROSSREFS
Cf. A001035 (column k=0), A000798 (main diagonal), A006059 (column k=1), A369778 (row sums), A006905, A369799.
Sequence in context: A279261 A185390 A361422 * A352811 A019116 A213611
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Jan 31 2024
STATUS
approved