login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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: A231256 A304120 A255929 * A003025 A015200 A331344
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:20 EDT 2024. Contains 371254 sequences. (Running on oeis4.)