|
%I M3161 #48 Jan 11 2022 13:20:13
%S 1,3,54,3834,1027080,1067308488,4390480193904,72022346388181584,
%T 4721717643249254751360,1237892809110149882059440768,
%U 1298060596773261804821355107253504,5444502293680983802677246555274553481984,91343781554246596956424128384394531707099632640
%N Number of weakly connected digraphs with n labeled nodes.
%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 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A003027/b003027.txt">Table of n, a(n) for n=1..30</a>
%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.
%F a(n) = A062738(n)/2^n, since binary relations = digraphs with loops. - _Ralf Stephan_ and _Vladeta Jovovic_, Mar 24 2004
%F E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).
%F a(n) = A053763(n) - (1/n) * Sum_{k=1..n-1} k*C(n,k)*a(k)*A053763(n-k). - _Geoffrey Critzer_, Oct 24 2012
%p b:= n-> 2^(n^2-n):
%p a:= proc(n) option remember; local k; `if`(n=0, 1,
%p b(n)- add(k*binomial(n,k) *b(n-k)*a(k), k=1..n-1)/n)
%p end:
%p seq(a(n), n=1..20); # _Alois P. Heinz_, Oct 21 2012
%t Range[0, 20]! CoefficientList[Series[D[1 + Log[Sum[2^(n^2 - n) x^n/n!, {n, 0, 20}]], x], {x, 0,20}], x]
%t c[n_]:=2^(n(n-1))-Sum[k Binomial[n,k]c[k] 2^((n-k)(n-k-1)),{k,1,n-1}]/n;c[0]=1;Table[c[i],{i,0,20}] (* _Geoffrey Critzer_, Oct 24 2012 *)
%o (PARI) v=Vec(log(sum(n=0, default(seriesprecision), 2^(n^2-n)*x^n/n!))); for(i=1, #v, v[i]*=(i-1)!); v \\ _Charles R Greathouse IV_, Feb 14 2011
%o (Sage)
%o b = lambda n: 2^(n^2-n)
%o @cached_function
%o def A003027(n):
%o return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
%o [A003027(n) for n in (1..13)] # _Peter Luschny_, Jan 18 2016
%Y The unlabeled case is A003085.
%Y Row sums of A062735.
%Y Cf. A053763 (not necessarily connected), A003030 (strongly connected).
%K nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_
%E Corrected and extended by _Vladeta Jovovic_, Goran Kilibarda
|
