cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

This page as a plain text file.
%I A366866 #16 Oct 26 2023 11:21:00
%S A366866 1,1,7,253,39463,24196201,56481554827,502872837857293,
%T A366866 17309567681965278223,2333553047265268677638161,
%U A366866 1243013506394568266481053180947,2629978323181659930952963974617537173,22170279317365870690118601982232935268994583
%N A366866 Number of binary relations R on [n] such that the transitive closure of R contains the identity relation.
%C A366866 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.
%C A366866 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.
%C A366866 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.
%C A366866 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.
%H A366866 D. A. Gregory, S. Kirkland, and N. J. Pullman, <a href="https://doi.org/10.1016/0024-3795(93)90323-G">Power convergent Boolean matrices</a>, Linear Algebra and its Applications, Volume 179, 15 January 1993, Pages 105-117.
%H A366866 E. de Panafieu and S. Dovgal, <a href="https://arxiv.org/abs/1903.09454">Symbolic method and directed graph enumeration</a>, arXiv:1903.09454 [math.CO], 2019.
%H A366866 S. Schwarz, <a href="http://dx.doi.org/10.21136/CMJ.1970.100989">On the semigroup of binary relations on a finite set </a>, Czechoslovak Mathematical Journal, 1970.
%F A366866 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).
%t A366866 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[
%t A366866   Series[1/ggf[Exp[- (s[2 x] - x)]], {x, 0, nn}], x]
%Y A366866 Cf. A366252, A003030, A000798.
%K A366866 nonn
%O A366866 0,3
%A A366866 _Geoffrey Critzer_, Oct 25 2023