A055328 Number of rooted identity trees with n nodes and 3 leaves.

1, 5, 13, 28, 53, 91, 146, 223, 326, 461, 634, 851, 1119, 1446, 1839, 2307, 2859, 3504, 4252, 5114, 6100, 7222, 8492, 9922, 11525, 13315, 15305, 17510, 19945, 22625, 25566, 28785, 32298, 36123, 40278, 44781, 49651, 54908, 60571, 66661

Offset: 6

Author

Christian G. Bower, May 12 2000

Keywords

• nonn
• easy

Examples

			Illustration for a(7)=5 from _N. J. A. Sloane_, Mar 21 2016:
The five 7-node rooted identity trees with 3 leaves are:
(O denotes the root)
o
|
o o o
|/ /
o o
|/
O
..........
o
|
o   o
|  /
o o o
|//
O
..........
o
|
o
|
o o
|/
o o
|/
O
..............
o
|
o o
|/
o
|
o o
|/
O
..............
o
|
o o
|/
o o
|/
o
|
O
..............
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 6..1000
• Index entries for sequences related to rooted trees
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,0,1,2,-3,1).

Crossrefs

Column 3 of A055327.

Programs

Magma

[(9*(1-(-1)^n) -272*n +216*n^2 -64*n^3 +6*n^4 +96*Floor((n+2)/3))/288: n in [6..46]]; // G. C. Greubel, Nov 09 2023

Mathematica

LinearRecurrence[{3,-2,-1,0,1,2,-3,1}, {1,5,13,28,53,91,146,223}, 40] (* Jean-François Alcover, Sep 06 2019 *)

PARI

Vec((2*x+1)/((1-x^2)*(1-x^3)*(1-x)^3) + O(x^40)) \\ Andrew Howroyd, Aug 28 2018

SageMath

[(9*(n%2) -136*n +108*n^2 -32*n^3 +3*n^4 +48*((n+2)//3))/144 for n in range(6,47)] # G. C. Greubel, Nov 09 2023

Formula

G.f.: x^6*(1+2*x)/((1-x^2)*(1-x^3)*(1-x)^3).

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-5) + 2*a(n-6) - 3*a(n-7) + a(n-8) for n>13. - Colin Barker, Sep 06 2019

a(n) = (1/288)*(41 - 240*n + 216*n^2 - 64*n^3 + 6*n^4 - 9*(-1)^n - 32*ChebyshevU(n, -1/2)). - G. C. Greubel, Nov 09 2023