|
|
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
|
|
|
FORMULA
|
E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).
|
|
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:
|
|
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
return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
|
|
CROSSREFS
|
Cf. A053763 (not necessarily connected), A003030 (strongly connected).
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|