cp's OEIS Frontend

A003030 Number of strongly connected digraphs with n labeled nodes.

%I A003030 M5064 #58 Jul 25 2024 11:06:11
%S A003030 1,1,18,1606,565080,734774776,3523091615568,63519209389664176,
%T A003030 4400410978376102609280,1190433705317814685295399296,
%U A003030 1270463864957828799318424676767488,5381067966826255132459611681511359329536,90765788839403090457244128951307413371883494400
%N A003030 Number of strongly connected digraphs with n labeled nodes.
%C A003030 As usual, there can be an edge both from i to j and from j to i.
%D A003030 Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
%D A003030 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 428.
%D A003030 R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D A003030 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.
%D A003030 R. W. Robinson, personal communication.
%D A003030 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
%D A003030 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003030 Vaclav Kotesovec, <a href="/A003030/b003030.txt">Table of n, a(n) for n = 1..58</a> (first 18 terms from R. W. Robinson)
%H A003030 Nicholas R. Beaton, <a href="https://arxiv.org/abs/2010.06955">Walks obeying two-step rules on the square lattice: full, half and quarter planes</a>, arXiv:2010.06955 [math.CO], 2020.
%H A003030 Huantian Cao, <a href="http://cobweb.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.
%H A003030 Huantian Cao, <a href="/A000009/a000009.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002 [Local copy, with permission]
%H A003030 A. Iványi, <a href="http://www.emis.de/journals/AUSM/C5-1/math51-5.pdf">Leader election in synchronous networks</a>, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
%H A003030 Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, <a href="https://arxiv.org/abs/2407.11877">Bridging Weighted First Order Model Counting and Graph Polynomials</a>, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
%H A003030 J. Ostroff, <a href="http://people.brandeis.edu/~gessel/homepage/students/ostroffthesis.pdf">Counting connected digraphs with gradings</a>, Phd. Thesis (2013), Table 1.
%H A003030 R. W. Robinson, <a href="/A003030/a003030.pdf">Letter to N. J. A. Sloane, 1980</a>
%F A003030 a(n) ~ 2^(n*(n-1)). - _Vaclav Kotesovec_, May 19 2015
%e A003030 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).
%p A003030 A003030 := proc(n)
%p A003030     option remember;
%p A003030     if n =1 then
%p A003030         1;
%p A003030     else
%p A003030         A054947(n)+add(binomial(n-1,t-1)*procname(t)*A054947(n-t),t=1..n-1) ;
%p A003030     end if;
%p A003030 end proc:
%p A003030 seq(A003030(n),n=1..10) ; # _R. J. Mathar_, May 10 2016
%t A003030 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}];
%t A003030 a[1]=1; a[n_]:=a[n]=b[n]+Sum[Binomial[n-1,j-1]*b[n-j]*a[j],{j,1,n-1}];
%t A003030 Table[a[n],{n,1,15}] (* _Vaclav Kotesovec_, May 19 2015 *)
%o A003030 (PARI) \\ here B(n) is A054947 as vector.
%o A003030 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}
%o A003030 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
%Y A003030 Cf. A035512, A054946 (strongly connected labeled tournaments), A054947.
%K A003030 nonn,nice
%O A003030 1,3
%A A003030 _N. J. A. Sloane_
%E A003030 a(12)-a(13) added by _Andrew Howroyd_, Sep 10 2018