A369799 Number of binary relations R on [n] such that q(R) is a quasi-order and s(R) is a strict partial order (where q(R) and s(R) are defined below).

1, 2, 13, 237, 11590, 1431913, 424559959, 292150780260, 456213083587511, 1589279411184268465, 12188163803127032036308, 203538148644721100472292979, 7336995548182992341725851094195, 566597426371900580541745092349604750, 93154354372753215966288131247384428212545, 32423220989898980232206367503220063835343283713

Offset

0,2

Comments

For a relation R on [n], let E = domain(R intersect R^(-1)) and let F = [n]\E. Then q(R) := R intersect E X E and let s(R) := R intersect F X F.

Links

Table of n, a(n) for n=0..15.

E. Norris, The structure of an idempotent relation, Semigroup Forum, Vol 18 (1979), 319-329.

Formula

a(n) = Sum_{k=0..n} A369776(n,k) * 3^(k*(n-k)).

Mathematica

nn = 18; 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[Total, (Map[Select[#, # > 0 &] &, Table[n!, {n, 0, nn}] CoefficientList[
      Series[ p[Exp[ y  x] - 1]*p[ x], {x, 0, nn}], {x, y}]])*
  Table[Table[3^(k (n - k)), {k, 0, n}], {n, 0, nn}]]

Crossrefs

Cf. A369778, A369776, A001035, A000798.

Sequence in context: A236903 A277452 A268703 * A187648 A113098 A365590

Adjacent sequences: A369796 A369797 A369798 * A369800 A369801 A369802

Keyword

nonn

Author

Geoffrey Critzer, Feb 01 2024

Status

approved