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

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

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

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