login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003027 Number of weakly connected digraphs with n labeled nodes.
(Formerly M3161)
18
1, 3, 54, 3834, 1027080, 1067308488, 4390480193904, 72022346388181584, 4721717643249254751360, 1237892809110149882059440768, 1298060596773261804821355107253504, 5444502293680983802677246555274553481984, 91343781554246596956424128384394531707099632640 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
REFERENCES
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
FORMULA
a(n) = A062738(n)/2^n, since binary relations = digraphs with loops. - Ralf Stephan and Vladeta Jovovic, Mar 24 2004
E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).
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
MAPLE
b:= n-> 2^(n^2-n):
a:= proc(n) option remember; local k; `if`(n=0, 1,
b(n)- add(k*binomial(n, k) *b(n-k)*a(k), k=1..n-1)/n)
end:
seq(a(n), n=1..20); # Alois P. Heinz, Oct 21 2012
MATHEMATICA
Range[0, 20]! CoefficientList[Series[D[1 + Log[Sum[2^(n^2 - n) x^n/n!, {n, 0, 20}]], x], {x, 0, 20}], x]
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 *)
PROG
(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
(Sage)
b = lambda n: 2^(n^2-n)
@cached_function
def A003027(n):
return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
[A003027(n) for n in (1..13)] # Peter Luschny, Jan 18 2016
CROSSREFS
The unlabeled case is A003085.
Row sums of A062735.
Cf. A053763 (not necessarily connected), A003030 (strongly connected).
Sequence in context: A171213 A006025 A049414 * A054545 A158103 A174579
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Corrected and extended by Vladeta Jovovic, Goran Kilibarda
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)