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

1, 6, 55, 540, 6412, 90734, 1515097, 29368155, 649910349, 16178495157, 447436384356, 13607804913248, 451277483034618, 16204761730619392, 626327433705523558, 25924177756443661632, 1144012780063556028591, 53615833082093775740400, 2659498185704802765924159

Offset

3,2

Links

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

Formula

a(n) ~ c * n^(n-2), where c = 0.130848879059... . - Vaclav Kotesovec, Sep 07 2014

Example

a(4) = 6:
.1-2.  .1 2.  .1 2.  .1 2.  .1 2.  .1 2.
.   .  .  |.  .   .  .|  .  . \ .  . / .
.4 3.  .4 3.  .4-3.  .4 3.  .4 3.  .4 3.

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, 3):
seq(a(n), n=3..25);

Mathematica

T[n_, k_] := T[n, k] = If[k<0 || k>n, 0, If[n == 0, 1, Sum[Binomial[n-1, i]*T[n-1-i, k-1]*If[i<2, 1, i!/2 + (i+1)^(i-1)], {i, 0, n-k}]]];
a[n_] := T[n, 3];
Table[a[n], {n, 3, 25}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)

Crossrefs

Column k=3 of A215861.

The unlabeled version is A215983.

Sequence in context: A318592 A342388 A253475 * A110431 A121661 A118836

Adjacent sequences: A215850 A215851 A215852 * A215854 A215855 A215856

Keyword

nonn

Author

Alois P. Heinz, Aug 25 2012

Status

approved