A365547 Triangular array read by rows. T(n,k) is the number of convergent Boolean relation matrices on [n] containing exactly k strongly connected components, n>=0, 0<=k<=n.

1, 0, 2, 0, 3, 12, 0, 139, 126, 200, 0, 25575, 17517, 9288, 8688, 0, 18077431, 8457840, 3545350, 1435920, 936992, 0, 47024942643, 14452288791, 4277647665, 1422744780, 485315280, 242016192

Offset

0,3

Links

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

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.

G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.

Formula

For n>=2, T(n,1) = A070322(n) and T(n,n) = A003024(n)*2^n.

Example

 Triangle begins ...
  1;
  0,        2;
  0,        3,      12;
  0,      139,     126,     200;
  0,    25575,   17517,    9288,    8688;
  0, 18077431, 8457840, 3545350, 1435920, 936992;
  ...

Mathematica

nn = 6; B[n_] := n! 2^Binomial[n, 2]; 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}]];
ggf[egf_] := Normal[Series[egf, {x, 0, nn}]] /. Table[x^i -> x^i/2^Binomial[i, 2], {i, 0, nn}]; Table[Take[(Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[-(y pr[x] - y + y x)]], {x, 0, nn}], {x, y}])[[i]], i], {i, 1, 7}] // Grid

Crossrefs

Cf. A365534 (row sums), A070322, A003024.

Sequence in context: A105418 A368584 A368583 * A280180 A337995 A337994

Adjacent sequences: A365544 A365545 A365546 * A365548 A365549 A365550

Keyword

nonn,tabl

Author

Geoffrey Critzer, Sep 08 2023

Status

approved