A067331 - OEIS

%I #110 Dec 06 2023 14:20:53

%S 2,5,12,25,50,96,180,331,600,1075,1908,3360,5878,10225,17700,30509,

%T 52390,89664,153000,260375,442032,748775,1265832,2136000,3598250,

%U 6052061,10164540,17048641,28559450,47786400,79870428,133359715,222457608,370747675,617363100

%N Convolution of Fibonacci F(n+1), n >= 0, with F(n+3), n >= 0.

%C Third diagonal of A067330. Third column of A067418.

%C From _Emeric Deutsch_, Jun 15 2010: (Start)

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

%C a(n) = Sum_{k>=0} k*A178524(n+2,k).

%C (End)

%C 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

%C 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

%D D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

%H Robert Israel, <a href="/A067331/b067331.txt">Table of n, a(n) for n = 0..4720</a>

%H Matthew Blair, Rigoberto Flórez, Antara Mukherjee, and José L. Ramírez, <a href="https://www.fq.math.ca/Papers1/58-5/blair2.pdf">Matrices in the determinant Hosoya triangle</a>, Fibonacci Quart. 58 (2020), no. 5, 34-54.

%H Matthew Blair, Rigoberto Flórez, and Antara Mukherjee, <a href="http://math.colgate.edu/~integers/v90/v90.pdf">Geometric Patterns in The Determinant Hosoya Triangle</a>, INTEGERS, A90, 2021.

%H J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, <a href="https://doi.org/10.37236/3478">Tiling a strip with triangles</a>, Electron. J. Combin. 21 (1) (2014), P1.7.

%H John M. Campbell, <a href="/A067331/a067331.pdf">On the external path length of a Fibonacci tree</a>.

%H Y. Horibe, <a href="http://www.fq.math.ca/Scanned/20-2/horibe.pdf">An entropy view of Fibonacci trees</a>, Fibonacci Quarterly, 20(2) (1982), 168-178.

%H S. Klavzar and M. Mollard, <a href="https://hal.archives-ouvertes.fr/hal-00836788">Asymptotic properties of Fibonacci cubes and Lucas cubes</a>, HAL Id: hal-00836788, 2013.

%H S. Klavzar and M. Mollard, <a href="https://doi.org/10.1007/s00026-014-0233-x">Asymptotic properties of Fibonacci cubes and Lucas cubes</a>, Ann. Comb. 18 (2014), 447-457.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,1,-2,-1).

%F a(n) = A067330(n+2, n) = A067418(n+2, 2) = Sum_{k=0..n} F(k+1)*F(n+3-k), n >= 0.

%F a(n) = ((7*n + 10)*F(n + 1) + 4*(n + 1)*F(n))/5, with F(n) = A000045(n) (Fibonacci).

%F G.f.: (2 + x)/(1 - x - x^2)^2.

%F a(n) = Sum_{i=0..floor((n+3)/2)} binomial(n+3-i, i)*(n + 2 - 2*i). - _John M. Campbell_, Jan 04 2016

%F 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

%e From _John M. Campbell_, Jan 03 2016: (Start)

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

%e      .

%e     / \

%e    /\ /\

%e   /\

%e (End)

%p 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):

%p map(f, [$0..50]); # _Robert Israel_, Jan 06 2016

%t LinearRecurrence[{2, 1, -2, -1}, {2, 5, 12, 25}, 70] (* _Vincenzo Librandi_, Jan 02 2016 *)

%t Table[SeriesCoefficient[(2 + x)/(1 - x - x^2)^2, {x, 0, n}], {n, 0, 34}] (* _Michael De Vlieger_, Jan 02 2016 *)

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

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

%o (Magma) [((7*n+10)*Fibonacci(n+1)+4*(n+1)*Fibonacci(n))/5: n in [0..40]]; // _Vincenzo Librandi_, Jan 02 2016

%o (PARI) Vec((2+x)/(1-x-x^2)^2 + O(x^100)) \\ _Altug Alkan_, Jan 04 2016

%Y Row sums of A108038.

%Y Cf. A000045, A004070, A067330, A067418, A178523, A178524.

%K nonn,easy,nice

%O 0,1

%A _Wolfdieter Lang_, Feb 15 2002