login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059167 Number of n-node labeled graphs without endpoints. 15
1, 1, 1, 2, 15, 314, 13757, 1142968, 178281041, 52610850316, 29702573255587, 32446427369694348, 69254848513798160815, 291053505824567573585744, 2421830049319361003822380177, 40050220743831370293688592267252 (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

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

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: A231256 A304120 A255929 * A003025 A015200 A030642

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 17:49 EST 2018. Contains 317323 sequences. (Running on oeis4.)