A365325 Triangular array read by rows. T(n,k) is the number of labeled digraphs (with self loops allowed) on [n] containing exactly k primitive components, n>=0, 0<=k<=n.

1, 1, 1, 4, 9, 3, 51, 298, 138, 25, 1831, 40815, 17853, 4494, 543, 166930, 23752151, 7418420, 1861755, 325895, 29281, 36681301, 55427713806, 10701675348, 2105585760, 391017795, 53021223, 3781503

Offset: 0

Author

Geoffrey Critzer, Oct 22 2023

Keywords

• nonn
• tabl

Comments

A primitive component (A070322) is a strongly connected component (A003030) such that the gcd of the lengths of its cycles is 1.

Examples

			Triangle begins
   1;
   1,     1;
   4,     9,     3;
  51,   298,   138,   25;
1831, 40815, 17853, 4494, 543;
...
		

Links

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

Crossrefs

Cf. A002416 (row sums), A003024 (main diagonal), A070322, A003030, A361269.

Programs

Mathematica

nn = 6; B[n_] := 2^Binomial[n, 2] n!; 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}]]; 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}];
Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[1/ggf[Exp[- (y (pr[x] - 1) + s[2 x] - (pr[x] - 1))]], {x,
      0, nn}], {x, y}]] // Grid

Formula

Sum_{n>=0} T(n,k)*y^k*x^n/(n!*2^binomial(n,2)) = 1/(E(x) @ exp(-(y*p(x)-1)+ s(2x) - (p(x)-1))) where E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)), p(x) is the e.g.f. for A070322, s(x) is the e.g.f. for A003030 and @ is the exponential Hadamard product (see Panafieu and Dovgal).