A361527 Triangular array read by rows. T(n,k) is the number of labeled digraphs on [n] having exactly k strongly connected components all of which are simple cycles, n >= 0, 0 <= k <= n.

1, 0, 1, 0, 1, 3, 0, 2, 21, 25, 0, 6, 213, 774, 543, 0, 24, 3470, 30275, 59830, 29281, 0, 120, 95982, 1847265, 7757355, 10110735, 3781503, 0, 720, 4578588, 190855000, 1522899105, 3944546095, 3767987307, 1138779265

Offset

0,6

Comments

Here, a strongly connected component containing exactly 1 vertex is considered a cycle.

Links

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

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.

Eric Weisstein's World of Mathematics, Simple Directed Graph

Wikipedia, Strongly connected component

Example

  1;
  0,  1;
  0,  1,   3;
  0,  2,  21,    25;
  0,  6, 213,   774,   543;
  0, 24,3470, 30275, 59830, 29281;
  ...

Mathematica

 nn = 7;
a[x_] := Log[1/(1 - x)];
begfa =Total[CoefficientList[ Series[1/(Total[ CoefficientList[Series[ Exp[-u *a[x]], {x, 0, nn}], x]* Table[z^n/(2^Binomial[n, 2]), {n, 0, nn}]]), {z, 0, nn}], z]*Table[z^n 2^Binomial[n, 2], {n, 0, nn}]];
Table[Take[(Range[0, nn]! CoefficientList[begfa, {z, u}])[[i]], i], {i, 1, nn + 1}] // Grid

Crossrefs

Cf. A011266 (row sums), A003024 (main diagonal), A000142 (column k=1).

Sequence in context: A302953 A350464 A247706 * A247704 A372344 A127802

Adjacent sequences: A361524 A361525 A361526 * A361528 A361529 A361530

Keyword

nonn,tabl

Author

Geoffrey Critzer, Mar 14 2023

Status

approved