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

 

Logo


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

1,3

COMMENTS

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

REFERENCES

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

LINKS

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

FORMULA

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(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

CROSSREFS

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

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

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