A059167 Number of n-node labeled graphs without endpoints.

1, 1, 1, 2, 15, 314, 13757, 1142968, 178281041, 52610850316, 29702573255587, 32446427369694348, 69254848513798160815, 291053505824567573585744, 2421830049319361003822380177, 40050220743831370293688592267252, 1319550593412053164173947687592553185

Offset

0,4

References

F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 31, problem 1.16(a).

Links

Robert Israel, Table of n, a(n) for n = 0..81

Marko R. Riedel, Geoffrey Critzer, Math.Stackexchange.com, Proof of the closed form of the e.g.f. by combinatorial species. - Marko Riedel, Sep 18 2016

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

a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, Sep 22 2016

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:
F(20); # Robert Israel, Sep 18 2016

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

Column k=0 of A327369.

Cf. A059166 (n-node connected labeled graphs without endpoints), A004108 (n-node connected unlabeled graphs without endpoints), A004110 (n-node unlabeled graphs without endpoints).

Sequence in context: A255929 A381988 A389387 * A003025 A015200 A331344

Adjacent sequences: A059164 A059165 A059166 * A059168 A059169 A059170

Keyword

easy,nonn

Author

Vladeta Jovovic, Jan 12 2001

Extensions

More terms from John Renze (jrenze(AT)yahoo.com), Feb 01 2001

Status

approved