A366218 Number of convergent binary relations on [n] (A365534) that converge to an equivalence relation (A000110).

1, 1, 4, 149, 26177, 18211032, 47135163595

Offset: 0

Author

Geoffrey Critzer, Oct 04 2023

Keywords

• nonn
• more

Comments

Equivalently, a(n) is the number of Boolean relation matrices whose Frobenius normal form is such that all the diagonal blocks are primitive (A070322) and all the off diagonal blocks are 0-blocks. See Gregory, Kirkland, Pullman.

The limit of a convergent binary relation R is an equivalence relation iff every vertex and every edge in G(R) is on a cycle, where G(R) is the directed graph with loops associated to R. See Corollary to Theorem 1 in Rosenblatt.

Links

• D. A. Gregory, S. Kirkland, and N. J. Pullman, Power convergent Boolean matrices, Linear Algebra and its Applications, Volume 179, 15 January 1993, pp. 105-117.
• 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, A000110.

Programs

Mathematica

nn = 13; B[n_] := 2^Binomial[n, 2] n!; primitive = Select[Import["https://oeis.org/A070322/b070322.txt", "Table"],
Length@# == 2 &][[All, 2]];pr[x_] := Total[primitive Table[x^i/i!, {i, 0, 6}]];Table[n!, {n, 0, nn}] CoefficientList[Series[Exp[pr[x] - 1], {x, 0, nn}], x]

Formula

E.g.f.: exp(p(x)-1) where p(x) is the e.g.f. for A070322.