login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Vaclav Kotesovec, Table of n, a(n) for n = 0..80

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!).

a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, May 14 2015

Logarithmic transform of A100743, if we assume a(1) = 0. - Gus Wiseman, Aug 15 2019

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)):

seq(a(n), n=0..20);  # Alois P. Heinz, Oct 27 2017

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).

Cf. A001187, A007146, A095983, A100743, A261919, A322395.

Sequence in context: A114450 A178689 A095983 * A100743 A251588 A126468

Adjacent sequences:  A059163 A059164 A059165 * A059167 A059168 A059169

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 14 16:21 EDT 2020. Contains 335729 sequences. (Running on oeis4.)