A215854 Number of simple labeled graphs on n nodes with exactly 4 connected components that are trees or cycles.

1, 10, 125, 1610, 23597, 394506, 7533445, 163190665, 3971678359, 107502644249, 3205669601953, 104435680520535, 3690517248021753, 140590728463023632, 5743180320999041664, 250423270549658253350, 11608409727652016747176, 570034426072900362961212

Offset

4,2

Links

Alois P. Heinz, Table of n, a(n) for n = 4..145

Example

a(4) = 1: the graph with 4 1-node trees.
a(5) = 10: each graph has one 2-node tree and 3 1-node trees, and C(5,2) = 10.

Maple

T:= proc(n, k) option remember; `if`(k<0 or k>n, 0,
      `if`(n=0, 1, add(binomial(n-1, i)*T(n-1-i, k-1)*
      `if`(i<2, 1, i!/2 +(i+1)^(i-1)), i=0..n-k)))
    end:
a:= n-> T(n, 4):
seq(a(n), n=4..25);

Crossrefs

Column k=4 of A215861.

The unlabeled version is A215984.

Sequence in context: A259839 A005174 A034668 * A123358 A230390 A089832

Adjacent sequences: A215851 A215852 A215853 * A215855 A215856 A215857

Keyword

nonn

Author

Alois P. Heinz, Aug 25 2012

Status

approved