A361579 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] with exactly k source-like components, n >= 0, 0 <= k <= n.

1, 0, 1, 0, 3, 1, 0, 51, 12, 1, 0, 3614, 447, 34, 1, 0, 991930, 53675, 2885, 85, 1, 0, 1051469032, 21514470, 741455, 16665, 201, 1, 0, 4366988803688, 30405612790, 642187105, 9816380, 90678, 462, 1, 0, 71895397383029040, 160152273169644, 2024633081100, 19625842425, 122330544, 474138, 1044, 1

Offset

0,5

Comments

Here, a source-like component of a digraph D is a strongly connected component of D that corresponds to a node of in-degree 0 in the condensation of D.

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.

Wikipedia, Strongly connected component

Example

Triangle begins:
  1;
  0,      1;
  0,      3,     1;
  0,     51,    12,    1;
  0,   3614,   447,   34,  1;
  0, 991930, 53675, 2885, 85, 1;
  ...

Mathematica

nn = 6; B[n_] := n! 2^Binomial[n, 2]; 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}]];
ggfz[egfx_] := Normal[Series[egfx, {x, 0, nn}]] /.Table[x^i -> z^i/2^Binomial[i, 2], {i, 0, nn}]; Table[B[n], {n, 0, nn}] CoefficientList[Series[ggfz[Exp[(u - 1) s[x]]]/ggfz[Exp[- s[x]]], {z, 0, nn}], {z u}] // Grid

Crossrefs

Cf. A003028 (column k=1), A053763 (row sums).

Sequence in context: A187558 A327547 A233293 * A066746 A278105 A074063

Adjacent sequences: A361576 A361577 A361578 * A361580 A361581 A361582

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 16 2023

Status

approved