login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A189940 Number of connected components in all simple labeled graphs with n nodes having degrees at most one. 1
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 02:41 EST 2018. Contains 299357 sequences. (Running on oeis4.)