A361269 Triangular array read by rows. T(n,k) is the number of binary relations on [n] containing exactly k strongly connected components, n >= 0, 0 <= k <= n.

1, 0, 2, 0, 4, 12, 0, 144, 168, 200, 0, 25696, 18768, 12384, 8688, 0, 18082560, 8697280, 3923040, 1914560, 936992, 0, 47025585664, 14670384000, 4512045120, 1622358720, 647087040, 242016192, 0, 450955726792704, 87781550054912, 17679638000640, 4496696041600, 1408276410240, 482302375296, 145763745920

Offset

0,3

Links

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

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.

Wikipedia, Strongly connected component

Formula

E.g.f. for column 1: A(2*x) where A(x) is the e.g.f. for A003030.

E.g.f. for main diagonal: B(2*x) where B(x) is the e.g.f. for A003024.

Example

  1;
  0,     2;
  0,     4,    12;
  0,   144,   168,   200;
  0, 25696, 18768, 12384, 8688;
  ...

Mathematica

nn =15; 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}]]; begf = Total[CoefficientList[ Series[1/(Total[CoefficientList[Series[ Exp[-u *s[x]], {x, 0, nn}], x]* Table[z^n/(2^Binomial[n, 2]), {n, 0, nn}]]), {z, 0, nn}], z]*Table[z^n 2^Binomial[n, 2], {n, 0, nn}]] /. z -> 2 z;
Range[0, nn]! CoefficientList[begf, {z, u}] // Grid (* Geoffrey Critzer, Mar 14 2023 after Andrew Howroyd *)

Prog

(PARI)
Z(p, f)={my(n=serprec(p, x)); serconvol(p, sum(k=0, n-1, x^k*f(k), O(x^n)))}
G(e, p)={Z(p, k->1/e^(k*(k-1)/2))}
U(e, p)={Z(p, k->e^(k*(k-1)/2))}
RelEgf(n, e)={sum(k=0, n, e^(k^2)*x^k/k!, O(x*x^n) )}
T(n)={my(e=2); [Vecrev(p) | p<-Vec(serlaplace(U(e, 1/G(e, exp(y*log(U(e, 1/G(e, RelEgf(n, e)))))))))]}
{ my(A=T(6)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 06 2023

Crossrefs

Cf. A003030, A003024, A002416 (row sums).

Sequence in context: A167341 A378853 A359188 * A343472 A214199 A320491

Adjacent sequences: A361266 A361267 A361268 * A361270 A361271 A361272

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 06 2023

Extensions

Terms a(15) and beyond from Andrew Howroyd, Mar 06 2023

Status

approved