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,3

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

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

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.

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).

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]

Crossrefs

Cf. A070322, A365534, A000798, A366218.

Sequence in context: A233142 A166502 A173083 * A338297 A084070 A282736

Adjacent sequences: A366249 A366250 A366251 * A366253 A366254 A366255

Keyword

nonn,more

Author

Geoffrey Critzer, Oct 05 2023

Status

approved