A339590 -id:A339590 - cp's OEIS frontend

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

1, 0, 0, 1, 0, 0, 0, 2, 9, 6, 1, 0, 0, 0, 0, 6, 84, 316, 492, 417, 212, 66, 12, 1, 0, 0, 0, 0, 0, 24, 720, 6440, 26875, 65280, 105566, 122580, 106825, 71700, 37540, 15344, 4835, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 0, 120, 6480, 107850, 868830, 4188696, 13715940

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,2,9,6,1;
  [4] 0,0,0,0,6,84,316,492,417,212,66,12,1;
  ...
Number of strongly connected digraphs on 3 labeled nodes is 18 = 2+9+6+1.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 2.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020. See Table 2.

Row sums give A003030.
The unlabeled version is A057276.
Cf. A057271, A057272, A057274, A057275, A062735.
Cf. A123554, A339590, A339807.

B(nn, e=2)={my(v=vector(nn)); for(n=1, nn, v[n] = e^(n*(n-1)) - sum(k=1, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[k])); v}
Strong(n, e=2)={my(u=B(n, e), v=vector(n)); v[1]=1; for(n=2, #v, v[n] = u[n] + sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v}
row(n)={ Vecrev(Strong(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 10 2022

Terms a(46) and beyond from Andrew Howroyd, Jan 10 2022

A339807 Irregular triangle read by rows: T(n,k) (n>=2, k>=1) is the number of strong digraphs on n nodes with k descents.

Original entry on oeis.org

1, 2, 11, 5, 10, 154, 540, 581, 272, 49, 122, 3418, 27304, 90277, 150948, 150519, 95088, 37797, 8714, 893, 3346, 142760, 1938178, 12186976, 42696630, 94605036, 145009210, 161845163, 134933733, 84656743, 39632149, 13481441, 3156845, 455917, 30649

Offset: 2

Hugo Pfoertner, Dec 28 2020

T(n,1) = A005321(n-1). Length of row n = binomial(n,2). It appears that T(n,binomial(n,2)) = A348901(n-1). - Geoffrey Critzer, Feb 12 2025

			Triangle begins:
 1;
 2, 11, 5;
 10, 154, 540, 581, 272, 49;
 122, 3418, 27304, 90277, 150948, 150519, 95088, 37797, 8714, 893;
 3346, 142760, 1938178, 12186976, 42696630, 94605036, 145009210, 161845163, 134933733, 84656743, 39632149, 13481441, 3156845, 455917, 30649;
 ...

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020.

Cf. A003030 (row sums), A057273 (another version of the same triangle), A307049, A339590, A005321, A000217.

nn = 8; B[n_] := FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]] (1 + y)^Binomial[n, 2]; g[z_] := Sum[(1 + u y)^Binomial[n, 2] z^n/FunctionExpand[QFactorial[n, (1 + u y)/(1 + y)]], {n, 0, nn}]; egf[eggf_] := Normal[Series[eggf, {z, 0, nn}]] /.Table[z^i -> z^i*B[i]/i!, {i, 1, nn + 1}]; Map[Drop[#, 1] &, Drop[Map[CoefficientList[#, u] &, Table[n!, {n, 0, nn}]CoefficientList[Series[-Log[egf[1/g[z]]], {z, 0, nn}], z] /. y -> 1], 2]] // Grid (* Geoffrey Critzer, Feb 12 2025 *)

Row 2 added by N. J. A. Sloane, Dec 29 2020

A307049 Irregular table read by rows: The number of acyclic digraphs on n labeled nodes with k descents.

Original entry on oeis.org

1, 2, 1, 8, 11, 5, 1, 64, 161, 167, 102, 39, 9, 1, 1024, 3927, 6698, 7185, 5477, 3107, 1329, 423, 96, 14, 1, 32768, 172665, 419364, 656733, 757939, 686425, 504084, 305207, 153333, 63789, 21752, 5959, 1267, 197, 20, 1, 2097152, 14208231, 45263175, 94040848, 145990526, 181444276, 187742937, 165596535

Offset: 1

R. J. Mathar, Mar 21 2019

			     1;
     2    1;
     8   11    5    1;
    64  161  167  102   39    9    1;
  1024 3927 6698 7185 5477 3107 1329 423 96 14 1;
...

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 3

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020. See Table 3.
K. Archer, C. Graves, Enumerating acyclic digraphs by descents, arXiv:1709.00601 [math.CO], 2017.

Cf. A003024 (row sums), A006125, A057273, A339590, A339807.

cp's OEIS Frontend

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A339807 Irregular triangle read by rows: T(n,k) (n>=2, k>=1) is the number of strong digraphs on n nodes with k descents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A307049 Irregular table read by rows: The number of acyclic digraphs on n labeled nodes with k descents.

Views

Author

Keywords

Examples

References

Links

Crossrefs