login
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.
0
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,4
COMMENTS
A primitive component (A070322) is a strongly connected component (A003030) such that the gcd of the lengths of its cycles is 1.
LINKS
E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
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).
EXAMPLE
Triangle begins
1;
1, 1;
4, 9, 3;
51, 298, 138, 25;
1831, 40815, 17853, 4494, 543;
...
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
CROSSREFS
Cf. A002416 (row sums), A003024 (main diagonal), A070322, A003030, A361269.
Sequence in context: A219731 A217393 A285323 * A321219 A178143 A070435
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Oct 22 2023
STATUS
approved