The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003030 Number of strongly connected digraphs with n labeled nodes.
(Formerly M5064)
1, 1, 18, 1606, 565080, 734774776, 3523091615568, 63519209389664176, 4400410978376102609280, 1190433705317814685295399296, 1270463864957828799318424676767488, 5381067966826255132459611681511359329536, 90765788839403090457244128951307413371883494400 (list; graph; refs; listen; history; text; internal format)



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


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


R. W. Robinson and 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.

J. Ostroff, Counting connected digraphs with gradings, Phd. Thesis (2013), Table 1.

R. W. Robinson, Letter to N. J. A. Sloane, 1980


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


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


A003030 := proc(n)

    option remember;

    if n =1 then



        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


Clear[a]; Clear[b]; 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 *)


(PARI) \\ 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


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

Sequence in context: A258336 A211310 A160307 * A276016 A086366 A086193

Adjacent sequences:  A003027 A003028 A003029 * A003031 A003032 A003033




N. J. A. Sloane


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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 17:32 EDT 2021. Contains 347607 sequences. (Running on oeis4.)