|
|
A185369
|
|
Number of simple labeled graphs on n nodes of degree 1 or 2 without cycles.
|
|
8
|
|
|
1, 0, 1, 3, 15, 90, 645, 5355, 50505, 532980, 6219045, 79469775, 1103335695, 16533226710, 265888247625, 4566885297975, 83422361847825, 1614626682669000, 33003508539026025, 710350201433547675, 16057073233633006575
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
REFERENCES
|
Herbert S. Wilf, Generatingfunctionology, p. 104.
|
|
LINKS
|
|
|
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:
|
|
MATHEMATICA
|
a=1/(2(1-x))-1/2-x/2;
Range[0, 20]! CoefficientList[Series[Exp[a], {x, 0, 20}], x]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|