login
Number of strongly connected digraphs with n labeled nodes.
(Formerly M5064)
33

%I M5064 #58 Jul 25 2024 11:06:11

%S 1,1,18,1606,565080,734774776,3523091615568,63519209389664176,

%T 4400410978376102609280,1190433705317814685295399296,

%U 1270463864957828799318424676767488,5381067966826255132459611681511359329536,90765788839403090457244128951307413371883494400

%N Number of strongly connected digraphs with n labeled nodes.

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

%D Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 428.

%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

%D 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 R. W. Robinson, personal communication.

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 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 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 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 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 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 R. W. Robinson, <a href="/A003030/a003030.pdf">Letter to N. J. A. Sloane, 1980</a>

%F a(n) ~ 2^(n*(n-1)). - _Vaclav Kotesovec_, May 19 2015

%e 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 := proc(n)

%p option remember;

%p if n =1 then

%p 1;

%p else

%p A054947(n)+add(binomial(n-1,t-1)*procname(t)*A054947(n-t),t=1..n-1) ;

%p end if;

%p end proc:

%p seq(A003030(n),n=1..10) ; # _R. J. Mathar_, May 10 2016

%t 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 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 Table[a[n],{n,1,15}] (* _Vaclav Kotesovec_, May 19 2015 *)

%o (PARI) \\ here B(n) is A054947 as vector.

%o 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 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 Cf. A035512, A054946 (strongly connected labeled tournaments), A054947.

%K nonn,nice

%O 1,3

%A _N. J. A. Sloane_

%E a(12)-a(13) added by _Andrew Howroyd_, Sep 10 2018