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
Keywords
Examples
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.
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).
Crossrefs
Programs
-
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 *)
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