A185369 Number of simple labeled graphs on n nodes of degree 1 or 2 without cycles.

1, 0, 1, 3, 15, 90, 645, 5355, 50505, 532980, 6219045, 79469775, 1103335695, 16533226710, 265888247625, 4566885297975, 83422361847825, 1614626682669000, 33003508539026025, 710350201433547675, 16057073233633006575

Offset

0,4

References

Herbert S. Wilf, Generatingfunctionology, p. 104.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..400

Formula

E.g.f.: exp(1/(2*(1-x))-x/2-1/2).

a(n) = 1-n if n<2, else a(n) = Sum_{k=2..n} C(n-1,k-1) * k!/2 * a(n-k).

a(n) ~ 2^(-3/4)*n^(n-1/4)*exp(-3/4+sqrt(2*n)-n). - Vaclav Kotesovec, Sep 25 2013

Conjecture: +2*a(n) +4*(-n+1)*a(n-1) +2*(n-1)*(n-3)*a(n-2) +(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Jun 14 2016

Example

a(4) = 15 because there are 15 simple labeled graphs on 4 nodes of degree 1 or 2 without cycles: 1-2 3-4, 1-3 2-4, 1-4 2-3, 1-2-3-4, 1-2-4-3, 1-3-2-4, 1-3-4-2, 1-4-2-3, 1-4-3-2, 2-1-3-4, 2-1-4-3, 3-1-2-4, 3-1-4-2, 4-1-2-3, 4-1-3-2.

Maple

a:= proc(n) option remember;
       `if`(n<2, 1-n, add(binomial(n-1, k-1) *k!/2 *a(n-k), k=2..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 24 2011

Mathematica

a=1/(2(1-x))-1/2-x/2;
Range[0, 20]! CoefficientList[Series[Exp[a], {x, 0, 20}], x]

Crossrefs

Sequence in context: A271930 A201953 A355501 * A024339 A319950 A336743

Adjacent sequences: A185366 A185367 A185368 * A185370 A185371 A185372

Keyword

nonn

Author

Geoffrey Critzer, Feb 20 2011

Status

approved