A362226 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k isolated strongly connected components, n>=0, 0<=k<=n.

1, 0, 1, 2, 1, 1, 36, 24, 3, 1, 2240, 1762, 87, 6, 1, 462720, 577000, 8630, 215, 10, 1, 332613632, 737645836, 3455820, 26085, 435, 15, 1, 867410804736, 3525456796232, 5166693532, 12154030, 61775, 777, 21, 1, 8503156728135680, 63526200994115056, 28215577119548, 20705805988, 32624585, 125776, 1274, 28, 1

Offset

0,4

Comments

Here, a strongly connected component is isolated if it is both an in-component and an out-component. A component is an in-component (out-component) if it corresponds to a node with outdegree (indegree) zero in the condensation of the digraph.

Links

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

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.

Formula

E.g.f.: exp((u-1)*S(z))*D(z) where S(z) is the e.g.f. for A003030 and D(z) is the e.g.f. for A053763.

Example

       1;
       0,      1;
       2,      1,    1;
      36,     24,    3,   1;
    2240,   1762,   87,   6,  1;
  462720, 577000, 8630, 215, 10, 1;
 ...

Mathematica

nn = 8; strong = Select[Import["https://oeis.org/A003030/b003030.txt", "Table"],
   Length@# == 2 &][[All, 2]]; s[z_] := Total[strong Table[z^i/i!, {i, 1, 58}]];
d[z_] := Sum[2^(n (n - 1)) z^n/n!, {n, 0, nn}]; Table[Take[(Table[n!, {n, 0, nn}] CoefficientList[ Series[Exp[(u - 1) s[z]] d[z], {z, 0, nn}], {z, u}])[[i]],
   i], {i, 1, nn + 1}] // Grid

Crossrefs

Cf. A217580, A361579, A003030, A053763.

Sequence in context: A093076 A132454 A182911 * A058293 A172092 A156888

Adjacent sequences: A362223 A362224 A362225 * A362227 A362228 A362229

Keyword

nonn,tabl

Author

Geoffrey Critzer, Apr 11 2023

Status

approved