A057276 -id:A057276 - cp's OEIS frontend

A035512 Number of unlabeled strongly connected digraphs with n nodes.

1, 1, 1, 5, 83, 5048, 1047008, 705422362, 1580348371788, 12139024825260556, 328160951349343885604, 31831080872412589394328804, 11234274997368899732057135454531, 14576252633139820879894296847900227082

Offset: 0

Ronald C. Read

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218.
V. A. Liskovets, A contribution to the enumeration of strongly connected digraphs, Dokl. AN BSSR, 17 (1973), 1077-1080, MR49#4849.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..18 from R. W. Robinson)
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 251. Book's website
Eric Weisstein's World of Mathematics, Strongly Connected Digraph.

The labeled version is A003030.
Row sums of A057276.
Column sums of A350753.
Cf. A003085, A049387, A350489, A350752.

\\ See PARI link in A350489 for program code.
A035512seq(15) \\ Andrew Howroyd, Jan 13 2022

a(12) and a(13) added by N. J. A. Sloane from the Robinson report, Oct 17 2006

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).

Original entry on oeis.org

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

A350752 Number of unlabeled strongly connected digraphs with n arcs.

Original entry on oeis.org

1, 0, 1, 1, 3, 6, 25, 91, 442, 2241, 12591, 75180, 478648, 3211245, 22635956, 166828221, 1281518573, 10229858290, 84652925554, 724601312400, 6403522811765, 58327076550161, 546764617643250, 5267719312771122, 52096218005705959, 528285485054771639

Offset: 0

Andrew Howroyd, Jan 13 2022

nonn

Row sums of A350753.
Column sums of A057276.
Cf. A035512, A350489, A350751.

A350752seq(20) \\ See PARI link in A350489 for program code.

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Original entry on oeis.org

1, 1, 0, 3, 4, 4, 1, 1, 0, 0, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008

Offset: 2

Vladeta Jovovic, Apr 21 2000

			1,1;
0,3,4,4,1,1;
0,0,8,22,37,47,38,27,13,5,1,1;
the last batch giving the numbers of connected digraphs with 4 nodes and from 1 to 12 arcs.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 2..2661 (rows 2..20)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 75.

Cf. A000238 (leading diagonal), A003085 (row sums), A053454 (column sums), A062735 (labeled).

Cf. A052283 (not necessarily connected), A283753 (another version), A057276 (strongly connected), A350789 (transpose).

InvEulerMTS(p)={my(n=serprec(p,x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i)}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^(2*g) )) * prod(i=1, #v, my(c=v[i]); t(c)^(c-1))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y)}
{ for(n=2, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

A057278 Triangle T(n,k) of number of digraphs with a source and a sink on n unlabeled nodes and k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 1, 4, 4, 1, 1, 0, 0, 0, 1, 11, 31, 45, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 1, 23, 152, 486, 992, 1419, 1641, 1485, 1152, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 1, 42, 517, 3194, 12174, 32860, 68423, 116168, 166164, 204867, 219906, 206993, 170922, 124088, 78809, 43860, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1],
  [0,1,1],
  [0,0,1,4,4,1,1],
  [0,0,0,1,11,31,45,38,27,13,5,1,1],
  ...
The number of digraphs with a source and a sink on 3 unlabeled nodes is 11 = 1+4+4+1+1.

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 246.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums give A049531.
Column sums give A350906.
The labeled version is A057271.
Cf. A057270, A057276, A057277, A057279, A350794, A350795.

\\ See PARI link in A350794 for program code.
{ my(A=A057278triang(5)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 21 2022

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

A057277 Triangle T(n,k) of number of digraphs with a source on n unlabeled nodes with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 1, 1, 0, 0, 2, 4, 4, 1, 1, 0, 0, 0, 4, 16, 34, 46, 38, 27, 13, 5, 1, 1, 0, 0, 0, 0, 9, 56, 229, 573, 1058, 1448, 1653, 1487, 1153, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 0, 20, 198, 1218, 5089, 15596, 37302, 72776, 119531, 168233, 205923, 220337, 207147, 170965, 124099, 78811, 43861, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1],
  [0, 1, 1],
  [0, 0, 2, 4, 4, 1, 1],
  [0, 0, 0, 4, 16, 34, 46, 38, 27, 13, 5, 1, 1],
  ....
The number of digraphs with a source on 3 unlabeled nodes is 12 = 2+4+4+1+1.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums give A051421.
Column sums give A350907.
The labeled version is A057274.
Cf. A057270, A057276, A057278, A057279, A350794, A350797.

\\ See PARI link in A350794 for program code.
{ my(A=A057277triang(5)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 21 2022

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

A350750 Triangle read by rows: T(n,k) is the number of strongly connected oriented graphs on n unlabeled nodes with k arcs, n >= 1, k = 0..n*(n-1)/2.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 5, 18, 27, 19, 6, 0, 0, 0, 0, 0, 0, 1, 8, 80, 333, 765, 1122, 1049, 622, 217, 35, 0, 0, 0, 0, 0, 0, 0, 1, 12, 221, 1875, 8971, 28449, 63845, 105556, 130935, 122607, 85926, 43868, 15506, 3403, 353

Offset: 1

Andrew Howroyd, Jan 13 2022

			Triangle begins:
  [1] 1;
  [2] 0, 0;
  [3] 0, 0, 0, 1;
  [4] 0, 0, 0, 0, 1, 2, 1;
  [5] 0, 0, 0, 0, 0, 1, 5, 18, 27,  19,   6;
  [6] 0, 0, 0, 0, 0, 0, 1,  8, 80, 333, 765, 1122, 1049, 622, 217, 35;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Row sums are A350489.
Column sums are A350751.
The labeled version is A350731.
Cf. A057276 (digraphs), A350733, A350734.

\\ See PARI link in A350489 for program code.
{ my(A=A350750rows(7)); for(n=1, #A, print(A[n])) }

A106238 Triangle read by rows: T(n,m) is the number of semi-strong digraphs on n unlabeled nodes with m connected components.

Original entry on oeis.org

1, 1, 1, 5, 1, 1, 83, 6, 1, 1, 5048, 88, 6, 1, 1, 1047008, 5146, 89, 6, 1, 1, 705422362, 1052471, 5151, 89, 6, 1, 1, 1580348371788, 706498096, 1052569, 5152, 89, 6, 1, 1, 12139024825260556, 1581059448174, 706503594, 1052574, 5152, 89, 6, 1, 1

Offset: 1

Washington Bomfim, May 01 2005

The formula T(n,m) is the sum over the partitions of n with m parts 1K1 + 2K2 + ... + nKn, of Product_{i=1..n} binomial(f(i) + Ki - 1, Ki) can be used to count unlabeled graphs of order n with m components if f(i) is the number of non-isomorphic connected components of order i. (In general, f denotes a sequence that counts unlabeled connected combinatorial objects.)

A digraph is semi-strong if all its weakly connected components are strongly connected. - Andrew Howroyd, Jan 14 2022

			Triangle begins:
          1;
          1,       1;
          5,       1,    1;
         83,       6,    1,  1;
       5048,      88,    6,  1, 1;
    1047008,    5146,   89,  6, 1, 1;
  705422362, 1052471, 5151, 89, 6, 1, 1;
  ...
T(4,2) = 6 because there are 6 digraphs of order 4 with 2 strongly connected components.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Row sums are A350754.
Column 1 is A035512.
Cf. A057276, A106237, A106239.

G.f.: 1/Product_{i>=1} (1-y*x^i)^A035512(i). - Vladeta Jovovic, May 04 2005

Triangle read by rows: T(n, m) is the sum over the partitions of n with m parts 1K1 + 2K2 + ... + nKn, of Product_{i=1..n} binomial(A035512(i) + Ki - 1, Ki).

Definition clarified by Andrew Howroyd, Jan 14 2022

A350753 Triangle read by rows: T(n,k) is the number of unlabeled strongly connected digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 4, 1, 0, 0, 0, 1, 16, 7, 1, 0, 0, 0, 0, 22, 58, 10, 1, 0, 0, 0, 0, 22, 240, 165, 14, 1, 0, 0, 0, 0, 11, 565, 1281, 365, 18, 1, 0, 0, 0, 0, 5, 928, 6063, 4838, 733, 23, 1, 0, 0, 0, 0, 1, 1065, 19591, 38516, 14661, 1317, 28, 1, 0

Offset: 0

Andrew Howroyd, Jan 14 2022

			Triangle begins:
  1;
  0, 0;
  0, 1, 0;
  0, 0, 1,  0;
  0, 0, 2,  1,   0;
  0, 0, 1,  4,   1,    0;
  0, 0, 1, 16,   7,    1,   0;
  0, 0, 0, 22,  58,   10,   1,  0;
  0, 0, 0, 22, 240,  165,  14,  1, 0;
  0, 0, 0, 11, 565, 1281, 365, 18, 1, 0;

Row sums are A350752.
Column sums are A035512.
Cf. A057276 (transpose), A350450, A350489.

\\ See PARI link in A350489 for program code.
my(A=A350753rows(10)); for(n=1, #A, print(A[n]))

cp's OEIS Frontend

A035512 Number of unlabeled strongly connected digraphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

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

A350752 Number of unlabeled strongly connected digraphs with n arcs.

Views

Author

Keywords

Crossrefs

Programs

PARI

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

A057278 Triangle T(n,k) of number of digraphs with a source and a sink on n unlabeled nodes and k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A057277 Triangle T(n,k) of number of digraphs with a source on n unlabeled nodes with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A350750 Triangle read by rows: T(n,k) is the number of strongly connected oriented graphs on n unlabeled nodes with k arcs, n >= 1, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A106238 Triangle read by rows: T(n,m) is the number of semi-strong digraphs on n unlabeled nodes with m connected components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A350753 Triangle read by rows: T(n,k) is the number of unlabeled strongly connected digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.