A133386 Number of forests of labeled rooted trees with n nodes, containing exactly 2 trees of height one, all others having height zero.

0, 0, 0, 0, 12, 120, 750, 3780, 16856, 69552, 272250, 1026300, 3762132, 13498056, 47615750, 165683700, 570024240, 1942538592, 6566094450, 22038141420, 73510278380, 243854707320, 804962754750, 2645408201700, 8658857196552, 28237920483600, 91778694166250

Offset

0,5

Links

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

A. P. Heinz, Finding Two-Tree-Factor Elements of Tableau-Defined Monoids in Time O(n^3), Ed. S. G. Akl, F. Fiala, W. W. Koczkodaj: Advances in Computing and Information, ICCI90 Niagara Falls, LNCS 468, Springer-Verlag (1990), pp. 120-128.

Index entries for linear recurrences with constant coefficients, signature (18,-141,630,-1767,3222,-3815,2826,-1188,216).

Formula

a(n) = n*(n-1) * Stirling2(n-1,3).

G.f.: -2*x^4*(85*x^4-180*x^3+141*x^2-48*x+6) / ((x-1)^3*(3*x-1)^3*(2*x-1)^3). - Maksym Voznyy (voznyy(AT)mail.ru), Jul 27 2009

a(0)=0, a(1)=0, a(2)=0, a(3)=0, a(4)=12, a(5)=120, a(6)=750, a(7)=3780, a(8)=16856, a(n)=18*a(n-1)-141*a(n-2)+630*a(n-3)-1767*a(n-4)+ 3222*a(n-5)- 3815*a(n-6)+2826*a(n-7)-1188*a(n-8)+216*a(n-9). - Harvey P. Dale, May 02 2015

Example

a(4) = 12 because 12 trees of the given kind exist: 1<-3 2<-4, 1<-4 2<-3, 1<-2 3<-4, 1<-4 3<-2, 1<-2 4<-3, 1<-3 4<-2, 2<-1 3<-4, 2<-4 3<-1, 2<-1 4<-3, 2<-3 4<-1, 3<-1 4<-2 and 3<-2 4<-1.

Maple

a:= n-> n*(n-1)*Stirling2(n-1, 3):
seq(a(n), n=0..50);

Mathematica

Join[{0}, Table[n(n-1)StirlingS2[n-1, 3], {n, 30}]] (* or *) LinearRecurrence[{18, -141, 630, -1767, 3222, -3815, 2826, -1188, 216}, {0, 0, 0, 0, 12, 120, 750, 3780, 16856}, 30] (* Harvey P. Dale, May 02 2015 *)

Crossrefs

Cf. A058877, A000248.

Column k=2 of A133399.

Column 2 of A198204. - Peter Bala, Aug 01 2012

Sequence in context: A093334 A001816 A354697 * A305624 A056320 A056311

Adjacent sequences: A133383 A133384 A133385 * A133387 A133388 A133389

Keyword

nonn

Author

Alois P. Heinz, Nov 22 2007

Status

approved