A366252 Number of convergent binary relations on [n] (A365534) that converge to a quasi-order relation (A000798).

1, 1, 6, 227, 37617, 23750562, 56091061929

Offset: 0

Author

Geoffrey Critzer, Oct 05 2023

Keywords

• nonn
• more

Comments

Equivalently, a(n) is the number of convergent Boolean relation matrices whose Frobenius normal form is such that all the diagonal blocks are primitive (A070322).

Links

• 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.
• D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Crossrefs

Cf. A070322, A365534, A000798, A366218.

Programs

Mathematica

nn = 6; B[n_] := 2^Binomial[n, 2] n!; pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];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[- (pr[x] - 1)]], {x, 0, nn}], x]

Formula

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