A185369 - OEIS

%I #32 Jun 17 2024 08:49:57

%S 1,0,1,3,15,90,645,5355,50505,532980,6219045,79469775,1103335695,

%T 16533226710,265888247625,4566885297975,83422361847825,

%U 1614626682669000,33003508539026025,710350201433547675,16057073233633006575

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

%D Herbert S. Wilf, Generatingfunctionology, p. 104.

%H Alois P. Heinz, <a href="/A185369/b185369.txt">Table of n, a(n) for n = 0..400</a>

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

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

%F a(n) ~ 2^(-3/4)*n^(n-1/4)*exp(-3/4+sqrt(2*n)-n). - _Vaclav Kotesovec_, Sep 25 2013

%F 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

%F a(n) = n! * Sum_{k=0..floor(n/2)} binomial(n-k-1,n-2*k)/(2^k * k!). - _Seiichi Manyama_, Jun 17 2024

%e 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.

%p a:= proc(n) option remember;

%p        `if`(n<2, 1-n, add(binomial(n-1, k-1) *k!/2 *a(n-k), k=2..n))

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Feb 24 2011

%t a=1/(2(1-x))-1/2-x/2;

%t Range[0,20]! CoefficientList[Series[Exp[a],{x,0,20}],x]

%Y Cf. A335344, A335345.

%Y Cf. A361533, A361545, A361547.

%K nonn

%O 0,4

%A _Geoffrey Critzer_, Feb 20 2011