|
|
A095340
|
|
Total number of nodes in all labeled graphs on n nodes.
|
|
10
|
|
|
1, 4, 24, 256, 5120, 196608, 14680064, 2147483648, 618475290624, 351843720888320, 396316767208603648, 885443715538058477568, 3929008913747544817795072, 34662321099990647697175478272, 608472288109550112718417538580480, 21267647932558653966460912964485513216
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Number of perfect matchings of an n X (n+1) Aztec rectangle with the second vertex in the topmost row removed.
|
|
REFERENCES
|
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, page 7
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n * 2^(n*(n-1)/2). E.g., a(7) = 7 * 2^(7*6/2) = 7 * 2097152 = 14680064. - David Terr, Nov 08 2004
a(n) = (32*a(n-1)*a(n-3)-48*a(n-2)^2)/a(n-4). - Michael Somos, Sep 16 2005
a(n) = Sum_{k=1..n} k*C(n,k)*2^C(n-k,2)*A001187(k). The sum gives the number of rooted labeled simple graphs on n nodes. It conditions on k, 1<=k<=n, the size of the connected component that the root is in. See Harary and Palmer reference. - Geoffrey Critzer, Nov 12 2011
|
|
MAPLE
|
a:= n-> n*2^(n*(n-1)/2):
|
|
MATHEMATICA
|
g = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, 20}]; a = Drop[Range[0, 20]! CoefficientList[Series[Log[g] + 1, {x, 0, 20}], x], 1]; Table[Sum[k Binomial[n, k] 2^Binomial[n - k, 2] a[[k]], {k, 1, n}], {n, 1, 20}] (* Geoffrey Critzer, Nov 12 2011 *)
|
|
PROG
|
(PARI) a(n)=n*2^((n^2-n)/2)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|