login
Number of connected components in all simple labeled graphs with n nodes having degrees at most one.
1

%I #21 Aug 22 2021 13:13:01

%S 1,3,9,28,90,306,1078,3984,15228,60580,248556,1055088,4606264,

%T 20712888,95550120,452450176,2193051408,10882018224,55166645008,

%U 285683655360,1508969248416,8127210649888,44582377997664,249000413522688,1414657929227200,8172653475494976

%N Number of connected components in all simple labeled graphs with n nodes having degrees at most one.

%C Equivalently, a(n) is the number of cycles in all self-inverse permutations of {1,2,...,n}.

%H Alois P. Heinz, <a href="/A189940/b189940.txt">Table of n, a(n) for n = 1..300</a>

%F E.g.f.: B(A(x)) where A(x) = x +x^2/2 and B(x) = x*exp(x).

%e a(3) = 9 because the self-inverse permutations of [3] are (given in their cycle notation): (1)(2)(3), (1)(2,3), (2)(1,3), (3)(1,2) and there are 9 cycles in all.

%p A:= x-> x*(x+2)/2:

%p B:= x-> x*exp(x):

%p a:= n-> n! *coeff(series(B(A(x)), x, n+1), x, n):

%p seq(a(n), n=1..30); # _Alois P. Heinz_, May 01 2011

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<5, [0, 1, 3, 9, 28][n+1],

%p (n*(n-5)*a(n-1)+n*(n-1)*(n-3)*a(n-2))/((n-1)*(n-4)))

%p end:

%p seq(a(n), n=1..30); # _Alois P. Heinz_, Feb 10 2014

%t a= x+x^2/2;Drop[Range[0,20]! CoefficientList[Series[a Exp[a],{x,0,20}],x],1]

%Y Cf. A000085.

%K nonn

%O 1,2

%A _Geoffrey Critzer_, May 01 2011