A035512 -id:A035512 - cp's OEIS frontend

A003030 Number of strongly connected digraphs with n labeled nodes.

1, 1, 18, 1606, 565080, 734774776, 3523091615568, 63519209389664176, 4400410978376102609280, 1190433705317814685295399296, 1270463864957828799318424676767488, 5381067966826255132459611681511359329536, 90765788839403090457244128951307413371883494400

Offset: 1

N. J. A. Sloane

As usual, there can be an edge both from i to j and from j to i.

			a(3) = 18 (the symbol = denotes a pair of parallel edges): 1->2->3->1 (2 such); 1=2->3->1 (6); 1=2=3->1 (6); 1=2=3=1 (1); 1=2=3 (3).

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 428.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vaclav Kotesovec, Table of n, a(n) for n = 1..58 (first 18 terms from R. W. Robinson)
Nicholas R. Beaton, Walks obeying two-step rules on the square lattice: full, half and quarter planes, arXiv:2010.06955 [math.CO], 2020.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
J. Ostroff, Counting connected digraphs with gradings, Phd. Thesis (2013), Table 1.
R. W. Robinson, Letter to N. J. A. Sloane, 1980

Cf. A035512, A054946 (strongly connected labeled tournaments), A054947.

A003030 := proc(n)
    option remember;
    if n =1 then
        1;
    else
        A054947(n)+add(binomial(n-1,t-1)*procname(t)*A054947(n-t),t=1..n-1) ;
    end if;
end proc:
seq(A003030(n),n=1..10) ; # R. J. Mathar, May 10 2016

b[1]=1; b[n_]:=b[n]=2^(n*(n-1))-Sum[Binomial[n,j]*2^((n-1)*(n-j))*b[j],{j,1,n-1}];
a[1]=1; a[n_]:=a[n]=b[n]+Sum[Binomial[n-1,j-1]*b[n-j]*a[j],{j,1,n-1}];
Table[a[n],{n,1,15}] (* Vaclav Kotesovec, May 19 2015 *)

\\ here B(n) is A054947 as vector.
B(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=2^(n*(n-1))-sum(j=1, n-1, binomial(n, j)*2^((n-1)*(n-j))*v[j])); v}
seq(n)={my(u=B(n), 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} \\ Andrew Howroyd, Sep 10 2018

a(n) ~ 2^(n*(n-1)). - Vaclav Kotesovec, May 19 2015

a(12)-a(13) added by Andrew Howroyd, Sep 10 2018

A003085 Number of weakly connected digraphs with n unlabeled nodes.

Original entry on oeis.org

1, 2, 13, 199, 9364, 1530843, 880471142, 1792473955306, 13026161682466252, 341247400399400765678, 32522568098548115377595264, 11366712907233351006127136886487, 14669074325902449468573755897547924182

Offset: 1

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 124 and 241.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Keith Briggs, Table of n, a(n) for n = 1..64
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Alexander G. Ginsberg, Firing-Rate Models in Computational Neuroscience: New Applications and Methodologies, Ph. D. Dissertation, Univ. Michigan, 2023. See p. 7.
Martin Golubitsky and Yangyang Wang, Infinitesimal homeostasis in three-node input-output networks, Journal of Mathematical Biology (2020) Vol. 80, 1163-1185.
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G. Wang, NetMODE: Network Motif Detection without Nauty, PLoS ONE 7(12): e50093. doi:10.1371/journal.pone.0050093. - From _N. J. A. Sloane_, Feb 02 2013
Eric Weisstein's World of Mathematics, Weakly Connected Digraph

Row sums of A054733.
Column sums of A350789.
The labeled case is A003027.
Cf. A000273, A003084, A035512 (strongly connected).

# The function EulerInvTransform is defined in A358451.
a := EulerInvTransform(A000273):
seq(a(n), n = 1..13); # Peter Luschny, Nov 21 2022

Needs["Combinatorica`"]; d[n_] := GraphPolynomial[n, x, Directed] /. x -> 1; max = 13; se = Series[ Sum[a[n]*x^n/n, {n, 1, max}] - Log[1 + Sum[ d[n]*x^n, {n, 1, max}]], {x, 0, max}]; sol = SolveAlways[ se == 0, x]; Do[ A003084[n] = a[n] /. sol[[1]], {n, 1, max}]; ClearAll[a, d]; a[n_] := (1/n)*Sum[ MoebiusMu[ n/d ] * A003084[d], {d, Divisors[n]} ]; Table[ a[n], {n, 1, max}] (* Jean-François Alcover, Feb 01 2012, after formula *)
terms = 13;
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
d[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
A003084 = CoefficientList[Log[Sum[d[n] x^n, {n, 0, terms+1}]] + O[x]^(terms + 1), x] Range[0, terms] // Rest;
a[n_] := (1/n)*Sum[MoebiusMu[n/d] * A003084[[d]], {d, Divisors[n]}];
Table[a[n], {n, 1, terms}] (* Jean-François Alcover, Aug 30 2019, after Andrew Howroyd in A003084 *)

from functools import lru_cache
from itertools import product, combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A003085(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024

a(n) = (1/n)*Sum_{d|n} mu(n/d)*A003084(d), where mu is Moebius function.

Inverse Euler transform of A000273. - Andrew Howroyd, Dec 27 2021

More terms from Vladeta Jovovic, Jan 09 2000

A350489 Number of strongly connected oriented graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 0, 1, 4, 76, 4232, 611528, 222688092, 205040866270, 484396550160186, 2987729989350536868, 48933147333828638153224, 2160018687398735805070288200, 260218032038985813416099131315377, 86440094822917159858790627703492969772

Offset: 0

Andrew Howroyd, Jan 01 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Andrew Howroyd, PARI Program, Jan 2022.
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.
Wikipedia, Strongly connected component

Row sums of A350750.
The labeled version is A350730.
Cf. A001174, A035512, A086345, A350751.

A350489seq(15) \\ See Links for program code.

A051421 Number of digraphs on n unlabeled nodes with a sink (or, with a source).

Original entry on oeis.org

1, 2, 12, 185, 8990, 1505939, 875542491, 1789247738400, 13018820342147705, 341188114831706152794, 32520852428719860881939391, 11366533535523591133597276823755, 14669006027884671703581740693080811331, 70315546525961698601351615055416574931833334

Offset: 1

Vladeta Jovovic

Here a sink is defined to be a node to which all other nodes have a directed path. - Andrew Howroyd, Dec 27 2021

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218 (incorrect version).
Ronald C. Read, email to N. J. A. Sloane, 28 August, 2000.

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

The labeled case is A003028.
Row sums of A057277.
Cf. A003085, A035512, A003088, A049531, A350415, A350360, A350794.

\\ See PARI link in A350794 for program code.
A051421seq(15) \\ Andrew Howroyd, Jan 21 2022

a(6) corrected and a(7) from Sean A. Irvine, Sep 11 2021

a(0)=1 removed and terms a(8) and beyond from Andrew Howroyd, Jan 21 2022

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

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 1, 4, 16, 22, 22, 11, 5, 1, 1, 0, 0, 0, 0, 0, 1, 7, 58, 240, 565, 928, 1065, 953, 640, 359, 150, 59, 16, 5, 1, 1, 0, 0, 0, 0, 0, 0, 1, 10, 165, 1281, 6063, 19591, 47049, 87690, 131927, 163632, 170720, 151238, 115122, 75357, 42745, 20891, 8877, 3224, 1039, 286, 76, 17, 5, 1, 1

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,1,2,1,1;
  [4] 0,0,0,0,1,4,16,22,22,11,5,1,1;
  ...
The number of strongly connected digraphs on 3 unlabeled nodes is 5 = 1+2+1+1.

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

Row sums give A035512.
Column sums give A350752.
The labeled version is A057273.
Cf. A054733, A057270, A057277, A057278, A057279, A350489.

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

Terms a(46) and beyond from Andrew Howroyd, Jan 13 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.

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Original entry on oeis.org

1, 2, 11, 173, 8675, 1483821, 870901739, 1786098545810, 13011539185371716, 341128981258340797839, 32519138088689298538132027, 11366354205366488038532562993809, 14668937734550708660348161757913398001, 70315451107713339843384354196009678853303102

Offset: 1

Vladeta Jovovic, Goran Kilibarda

Here a source is defined to be a node which has a directed path to all other nodes and a sink to be a node to which all other nodes have a directed path. A digraph with a source and a sink can also be described as initially-finally connected. - Andrew Howroyd, Jan 01 2022

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

Row sums of A057278.
The labeled version is A049524.
Cf. A003085, A035512, A003088, A051421, A345258, A350794.

\\ See PARI link in A350794 for program code.
A049531seq(15) \\ Andrew Howroyd, Jan 21 2022

a(6)-a(7) from Andrew Howroyd, Jan 01 2022

Terms a(8) and beyond from Andrew Howroyd, Jan 20 2022

A003088 Number of unilateral digraphs with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 11, 171, 8603, 1478644, 870014637

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218.
Ronald C. Read, email to N. J. A. Sloane, 28 August, 2000.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson, Counting strong digraphs (research announcement), J. Graph Theory 1, 1977, pp. 189-190.

Cf. A057270, A003029 (labeled case), A003085, A035512, A051421, A049531, A049512.

Note that Read and Wilson incorrectly give a(4) as 172 - thanks to Vladeta Jovovic, Goran Kilibarda for finding this error and for verifying a(5).

a(7) from Sean A. Irvine, Jan 26 2015

A049512 Number of quasi-initially connected digraphs on n unlabeled nodes.

Original entry on oeis.org

1, 2, 13, 197, 9312, 1528634, 880277970

Offset: 1

Vladeta Jovovic, Goran Kilibarda

From Sean A. Irvine, Aug 01 2021: (Start)
A quasi-initially connected digraph is a digraph containing at least one vertex v such that every vertex u in the graph can either be reached from v or v can be reached from u (while obeying the directions on the edges).
There is no known formula. (End)

Sean A. Irvine, Java program (github)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Cf. A049414, A003085, A035512, A003088, A051421.

a(6)-a(7) from Sean A. Irvine, Aug 01 2021

A054951 Number of unlabeled semi-strong digraphs on n nodes with mutually nonisomorphic components.

Original entry on oeis.org

1, 1, 4, 78, 4960, 1041872, 704369984, 1579641879248, 12137443766888448, 328148810741254606592, 31830752699315833628787200, 11234243165959817684710307801600, 14576241398832991116522929933694031872, 70075699209573863790264288901653500497274880

Offset: 1

N. J. A. Sloane, May 24 2000

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

V. A. Liskovets, A contribution to the enumeration of strongly connected digraphs, Dokl. AN BSSR, 17 (1973), 1077-1080 (Russian), MR49#4849.

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A035512, A049387, A054952, A054953, A054954.

m = 15;
A035512 = Cases[Import["https://oeis.org/A035512/b035512.txt", "Table"], {, }][[All, 2]];
gf = 1 - Product[(1 - x^n)^A035512[[n + 1]], {n, 1, m}];
CoefficientList[gf + O[x]^m , x] // Rest (* Jean-François Alcover, Aug 26 2019, after Andrew Howroyd *)

G.f.: 1 - Product_{n > 0} (1 - x^n)^A035512(n). - Andrew Howroyd, Sep 10 2018

More terms from Vladeta Jovovic, Mar 11 2003

a(12)-a(14) from Andrew Howroyd, Sep 10 2018

cp's OEIS Frontend

A003030 Number of strongly connected digraphs with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003085 Number of weakly connected digraphs with n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A350489 Number of strongly connected oriented graphs on n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A051421 Number of digraphs on n unlabeled nodes with a sink (or, with a source).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A350752 Number of unlabeled strongly connected digraphs with n arcs.

Views

Author

Keywords

Crossrefs

Programs

PARI

A049531 Number of digraphs with a source and a sink on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A003088 Number of unilateral digraphs with n unlabeled nodes.

Views

Author

Keywords