|
|
A067331
|
|
Convolution of Fibonacci F(n+1), n >= 0, with F(n+3), n >= 0.
|
|
19
|
|
|
2, 5, 12, 25, 50, 96, 180, 331, 600, 1075, 1908, 3360, 5878, 10225, 17700, 30509, 52390, 89664, 153000, 260375, 442032, 748775, 1265832, 2136000, 3598250, 6052061, 10164540, 17048641, 28559450, 47786400, 79870428, 133359715, 222457608, 370747675, 617363100
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
a(n) is the external path length of the Fibonacci tree of order n+3. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node. The external path length of a tree is the sum of the levels of its external nodes (i.e., leaves).
a(n) = Sum_{k>=0} k*A178524(n+2,k).
(End)
a(n) equals the penultimate immanant of the (n+3) X (n+3) tridiagonal matrix with ones along the main diagonal, the superdiagonal, and the subdiagonal. - John M. Campbell, Jan 01 2016
a(n) is the sum of the eccentricities of the vertices of the Fibonacci cube G(n+1). Example: a(1)=5; indeed, the Fibonacci cube G(2) is the path graph P(3), the vertices of which have eccentricities 2, 1, 2. - Emeric Deutsch, May 28 2017
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = A067330(n+2, n) = A067418(n+2, 2) = Sum_{k=0..n} F(k+1)*F(n+3-k), n >= 0.
a(n) = ((7*n + 10)*F(n + 1) + 4*(n + 1)*F(n))/5, with F(n) = A000045(n) (Fibonacci).
G.f.: (2 + x)/(1 - x - x^2)^2.
a(n) = Sum_{i=0..floor((n+3)/2)} binomial(n+3-i, i)*(n + 2 - 2*i). - John M. Campbell, Jan 04 2016
E.g.f.: exp(x/2)*(50 + 55*x)*cosh(sqrt(5)*x/2) + sqrt(5)*(18 + 25*x)*sinh(sqrt(5)*x/2))/25. - Stefano Spezia, Dec 04 2023
|
|
EXAMPLE
|
Letting n=2, the external path length of the Fibonacci tree T(5) of order n+3=5 illustrated below is 12 = a(2) = F(1)*F(5) + F(2)*F(4) + F(3)*F(3).
.
/ \
/\ /\
/\
(End)
|
|
MAPLE
|
f:= gfun:-rectoproc({a(n) = 2*a(n-1)+a(n-2) - 2*a(n-3)-a(n-4), a(0)=2, a(1)=5, a(2)=12, a(3)=25}, a(n), remember):
|
|
MATHEMATICA
|
LinearRecurrence[{2, 1, -2, -1}, {2, 5, 12, 25}, 70] (* Vincenzo Librandi, Jan 02 2016 *)
Table[SeriesCoefficient[(2 + x)/(1 - x - x^2)^2, {x, 0, n}], {n, 0, 34}] (* Michael De Vlieger, Jan 02 2016 *)
Print[Table[Sum[Binomial[n + 3 - i, i]*(n + 2 - 2*i), {i, 0, Floor[(n + 3)/2]}], {n, 0, 100}]] (* John M. Campbell, Jan 04 2016 *)
Module[{nn=40, fibs}, fibs=Fibonacci[Range[nn]]; Table[ListConvolve[Take[ fibs, n], Take[fibs, {2, n+2}]], {n, nn-2}]][[All, 2]] (* Harvey P. Dale, Aug 03 2019 *)
|
|
PROG
|
(Magma) [((7*n+10)*Fibonacci(n+1)+4*(n+1)*Fibonacci(n))/5: n in [0..40]]; // Vincenzo Librandi, Jan 02 2016
(PARI) Vec((2+x)/(1-x-x^2)^2 + O(x^100)) \\ Altug Alkan, Jan 04 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|