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,2

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

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

Example

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

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

Prog

(PARI) Vec((2*x+1)/((1-x^2)*(1-x^3)*(1-x)^3) + O(x^40)) \\ Andrew Howroyd, Aug 28 2018
(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
(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

Crossrefs

Column 3 of A055327.

Sequence in context: A175254 A211636 A294172 * A027962 A023537 A023653

Adjacent sequences: A055325 A055326 A055327 * A055329 A055330 A055331

Keyword

nonn,easy

Author

Christian G. Bower, May 12 2000

Status

approved