|
| |
|
|
A059166
|
|
Number of n-node connected labeled graphs without endpoints.
|
|
21
|
|
|
|
1, 1, 0, 1, 10, 253, 12058, 1052443, 169488200, 51045018089, 29184193354806, 32122530765469967, 68867427921051098084, 290155706369032525823085, 2417761578629525173499004146, 40013923790443379076988789688611, 1318910080173114018084245406769861936
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 404.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{i=0..n} (-1)^i*binomial(n, i)*c(n-i)*(n-i)^i, for n>2, a(0)=1, a(1)=1, a(2)=0, where c(n) is number of n-node connected labeled graphs (cf. A001187).
E.g.f.: 1 + x^2/2 + log(Sum_{n >= 0} 2^binomial(n, 2)*(x*exp(-x))^n/n!).
|
|
|
MAPLE
|
c:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-
add(k*binomial(n, k)*2^((n-k)*(n-k-1)/2)*c(k), k=1..n-1)/n)
end:
a:= n-> max(0, add((-1)^i*binomial(n, i)*c(n-i)*(n-i)^i, i=0..n)):
|
|
|
MATHEMATICA
|
Flatten[{1, 1, 0, Table[n!*Sum[(-1)^(n-j)*SeriesCoefficient[1+Log[Sum[2^(k*(k-1)/2)*x^k/k!, {k, 0, j}]], {x, 0, j}]*j^(n-j)/(n-j)!, {j, 0, n}], {n, 3, 15}]}] (* Vaclav Kotesovec, May 14 2015 *)
c[0] = 1; c[n_] := c[n] = 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k)*(n - k - 1)/2)*c[k], {k, 1, n-1}]/n; a[0] = a[1] = 1; a[2] = 0; a[n_] := Sum[(-1)^i*Binomial[n, i]*c[n-i]*(n-i)^i, {i, 0, n}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 27 2017, using Alois P. Heinz's code for c(n) *)
|
|
|
PROG
|
(PARI) seq(n)={Vec(serlaplace(1 + x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!))))} \\ Andrew Howroyd, Sep 09 2018
|
|
|
CROSSREFS
|
Cf. A059167 (n-node labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A004110 (n-node unlabeled graphs without endpoints).
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from John Renze (jrenze(AT)yahoo.com), Feb 01 2001
|
|
|
STATUS
|
approved
|
| |
|
|
