A366252 -id:A366252 - cp's OEIS frontend

A366866 Number of binary relations R on [n] such that the transitive closure of R contains the identity relation.

1, 1, 7, 253, 39463, 24196201, 56481554827, 502872837857293, 17309567681965278223, 2333553047265268677638161, 1243013506394568266481053180947, 2629978323181659930952963974617537173, 22170279317365870690118601982232935268994583

Offset: 0

Geoffrey Critzer, Oct 25 2023

nonn

Equivalently, a(n) is the number of n X n Boolean relation matrices whose Frobenius normal form contains no 0-blocks on the diagonal.  See Gregory, Kirkland, and Pullman.
Equivalently, a(n) is the number of labeled directed graphs on [n] (with self loops allowed) such that every strongly connected component contains at least one arc.
This sequence is a good upper-bound for the number of relations that converge to a quasi-order (A366252) which is only known for n <= 6.
If the transitive closure of a relation R contains the identity relation then there is exactly one transitive relation in {R,R^2,R^3...}.  See Schwarz link.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
S. Schwarz, On the semigroup of binary relations on a finite set , Czechoslovak Mathematical Journal, 1970.

Cf. A366252, A003030, A000798.

nn = 12; B[n_] := 2^Binomial[n, 2] n!; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i,1,58}]];ggf[egf_]:=Normal[Series[egf, {x, 0, nn}]] /.Table[x^i ->x^i/2^Binomial[i, 2], {i, 0, nn}];Table[B[n], {n, 0, nn}] CoefficientList[
  Series[1/ggf[Exp[- (s[2 x] - x)]], {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(2^n*binomial(n,2)) = 1/(E(x) @ exp(-(s(2x)-x))) where E(x) = Sum_{n>=0} x^n/(2^n*binomial(n,2)), s(x) is the e.g.f. for A003030, and @ is the exponential Hadamard product (see Panafieu and Dovgal).

A369397 Number of binary relations R on [n] such that the (unique) idempotent in {R,R^2,R^3,...} is an equivalence relation.

Original entry on oeis.org

1, 1, 5, 157, 26345, 18218521, 47136254765, 451286947588597, 16264532016440908625, 2253156851039460378774961, 1219026648017155982267265596885, 2601923405098893502520360223043594957, 22040885615442635622424409144799379027505465

Offset: 0

Geoffrey Critzer, Jan 22 2024

nonn

Equivalently, a(n) is the number of binary relations R on [n] such that the Frobenius normal form has no 0-blocks on the diagonal and all off diagonal blocks are 0-blocks.

D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
S. Schwarz, On the semigroup of binary relations on a finite set , Czechoslovak Mathematical Journal, 1970.

Cf. A366866 (binary relations R on [n] such that the (unique) idempotent in {R,R^2,R^3,...} is a quasiorder), A365534, A366218, A365590, A355612, A365593, A366252, A366350, A366218.

nn = 12; strong =Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[x_] := Total[strong Table[x^i/i!, {i, 1, 58}]];
Table[n!, {n, 0, nn}] CoefficientList[Series[Exp [s[2 x] - x], {x, 0, nn}], x]

E.g.f.: exp(s(2x)-x) where s(x) is the e.g.f. for A003030.

cp's OEIS Frontend

A366866 Number of binary relations R on [n] such that the transitive closure of R contains the identity relation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula