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

%I #10 Mar 16 2023 19:46:07

%S 1,0,1,1,0,3,18,21,0,25,1699,1080,774,0,543,587940,267665,103860,

%T 59830,0,29281,750744901,225144360,64169325,19791000,10110735,0,

%U 3781503,3556390155318,672637205149,126726655860,29445913175,7939815030,3767987307,0,1138779265

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

%H E. de Panafieu and S. Dovgal, <a href="https://arxiv.org/abs/1903.09454">Symbolic method and directed graph enumeration</a>, arXiv:1903.09454 [math.CO], 2019.

%H R. W. Robinson, <a href="http://cobweb.cs.uga.edu/~rwr/publications/components.pdf">Counting digraphs with restrictions on the strong components</a>, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Strongly_connected_component">Strongly connected component</a>

%e Triangle begins:

%e 1;

%e 0, 1;

%e 1, 0, 3;

%e 18, 21, 0, 25;

%e 1699, 1080, 774, 0, 543;

%e 587940, 267665, 103860, 59830, 0, 29281;

%e ...

%t nn = 7; 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[Take[(Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggfz[Exp[-(s[x] - x + u x)]], {z, 0, nn}], {z,u}])[[i]], i], {i, 1, nn + 1}] // Grid

%Y Cf. A086366 (column k=0), A003024 (main diagonal), A053763 (row sums), A361590 (unlabeled version).

%K nonn,tabl

%O 0,6

%A _Geoffrey Critzer_, Mar 16 2023