cp's OEIS Frontend

A003027 Number of weakly connected digraphs with n labeled nodes.

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