A215862 Number of simple labeled graphs on n+2 nodes with exactly n connected components that are trees or cycles.

0, 4, 19, 55, 125, 245, 434, 714, 1110, 1650, 2365, 3289, 4459, 5915, 7700, 9860, 12444, 15504, 19095, 23275, 28105, 33649, 39974, 47150, 55250, 64350, 74529, 85869, 98455, 112375, 127720, 144584, 163064, 183260, 205275, 229215, 255189, 283309, 313690, 346450

Offset

0,2

Comments

Partial sums of A077414. [Bruno Berselli, Jul 30 2015]

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (5, -10, 10, -5, 1).

Formula

G.f.: (x-4)*x/(x-1)^5.

a(n) = C(n+2,3)*(3*n+13)/4.

a(n) = 5*a(n-1)- 10*a(n-2)+ 10*a(n-3) -5*a(n-4)+a(n-5), n>4. - Harvey P. Dale, Sep 10 2012

a(n) = 1/n! * Sum_{j=0..n} C(n,j)*(-1)^(n-j)*(j)^(n+1)*(j-1)). - Vladimir Kruchinin, Jun 06 2013

a(n) = 4*A000332(n+2) - A000332(n+1). - R. J. Mathar, Aug 12 2013

a(n) = Sum_{i=0..n} (3+i)*A000217(i). [Bruno Berselli, Apr 29 2014]

Example

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

Maple

a:= n-> binomial(n+2, 3)*(3*n+13)/4:
seq(a(n), n=0..40);

Mathematica

Table[Binomial[n+2, 3] (3n+13)/4, {n, 0, 40}] (* or *) LinearRecurrence[ {5, -10, 10, -5, 1}, {0, 4, 19, 55, 125}, 40] (* Harvey P. Dale, Sep 10 2012 *)

Crossrefs

A diagonal of A215861.

Regarding the sixth formula, see similar sequences listed in A241765.

Cf. A000332, A077414.

Sequence in context: A186310 A122684 A122681 * A174612 A020496 A108484

Adjacent sequences: A215859 A215860 A215861 * A215863 A215864 A215865

Keyword

nonn,easy

Author

Alois P. Heinz, Aug 25 2012

Status

approved