|
|
A059167
|
|
Number of n-node labeled graphs without endpoints.
|
|
30
|
|
|
1, 1, 1, 2, 15, 314, 13757, 1142968, 178281041, 52610850316, 29702573255587, 32446427369694348, 69254848513798160815, 291053505824567573585744, 2421830049319361003822380177, 40050220743831370293688592267252, 1319550593412053164173947687592553185
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
REFERENCES
|
F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 31, problem 1.16(a).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{i=0..n-1} binomial(n-1, i)*b(i+1)*a(n-i-1), n>0, a(0)=1, where b(n) is number of n-node connected labeled graphs without endpoints (Cf. A059166).
E.g.f.: exp(x^2/2)*(Sum_{n >= 0} 2^binomial(n, 2)*(x/exp(x))^n/n!). - Vladeta Jovovic, Mar 23 2004
|
|
MAPLE
|
F:= proc(N) local S;
S:= series(exp(1/2*x^2)*Sum(2^binomial(n, 2)*(x/exp(x))^n/n!, n = 0 .. N), x, N+1);
seq(coeff(S, x, i)*i!, i=0..N)
end proc:
|
|
MATHEMATICA
|
b[n_] := If[n < 3, Boole[n == 1], 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}]]; a[0] = 1; a[n_] := a[n] = Sum[Binomial[n - 1, i] b[i + 1] a[n - i - 1], {i, 0, n - 1}]; Table[a@ n, {n, 0, 15}] (* Michael De Vlieger, Sep 19 2016, after Vaclav Kotesovec at A059166 *)
|
|
PROG
|
(PARI) seq(n)={my(A=x/exp(x + O(x^n))); Vec(serlaplace(exp(x^2/2 + O(x*x^n)) * sum(k=0, n, 2^binomial(k, 2)*A^k/k!)))} \\ Andrew Howroyd, Sep 09 2018
|
|
CROSSREFS
|
Cf. A059166 (n-node connected 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
|
|
|
|