OFFSET
0,1
COMMENTS
From Emeric Deutsch, Jun 15 2010: (Start)
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
Robert Israel, Table of n, a(n) for n = 0..4720
Matthew Blair, Rigoberto Flórez, Antara Mukherjee, and José L. Ramírez, Matrices in the determinant Hosoya triangle, Fibonacci Quart. 58 (2020), no. 5, 34-54.
Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, Geometric Patterns in The Determinant Hosoya Triangle, INTEGERS, A90, 2021.
J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with triangles, Electron. J. Combin. 21 (1) (2014), P1.7.
John M. Campbell, On the external path length of a Fibonacci tree.
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20(2) (1982), 168-178.
S. Klavzar and M. Mollard, Asymptotic properties of Fibonacci cubes and Lucas cubes, HAL Id: hal-00836788, 2013.
S. Klavzar and M. Mollard, Asymptotic properties of Fibonacci cubes and Lucas cubes, Ann. Comb. 18 (2014), 447-457.
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).
FORMULA
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
From John M. Campbell, Jan 03 2016: (Start)
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):
map(f, [$0..50]); # Robert Israel, Jan 06 2016
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
Wolfdieter Lang, Feb 15 2002
STATUS
approved