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

1, 3, 9, 28, 90, 306, 1078, 3984, 15228, 60580, 248556, 1055088, 4606264, 20712888, 95550120, 452450176, 2193051408, 10882018224, 55166645008, 285683655360, 1508969248416, 8127210649888, 44582377997664, 249000413522688, 1414657929227200, 8172653475494976

Offset

1,2

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 1..300

Formula

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

Example

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.

Maple

A:= x-> x*(x+2)/2:
B:= x-> x*exp(x):
a:= n-> n! *coeff(series(B(A(x)), x, n+1), x, n):
seq(a(n), n=1..30);  # Alois P. Heinz, May 01 2011
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [0, 1, 3, 9, 28][n+1],
      (n*(n-5)*a(n-1)+n*(n-1)*(n-3)*a(n-2))/((n-1)*(n-4)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 10 2014

Mathematica

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

Crossrefs

Cf. A000085.

Sequence in context: A071724 A000245 A143739 * A047047 A071744 A071748

Adjacent sequences: A189937 A189938 A189939 * A189941 A189942 A189943

Keyword

nonn

Author

Geoffrey Critzer, May 01 2011

Status

approved