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

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

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

Examples

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

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

Crossrefs

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

Programs

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

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

Formula

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

Extensions

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