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

Author

Alois P. Heinz, Aug 25 2012

Keywords

• nonn
• easy

Comments

Partial sums of A077414. - Bruno Berselli, Jul 30 2015

Examples

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

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).

Crossrefs

A diagonal of A215861.

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

Cf. A000332, A077414.

Programs

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 *)

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