cp's OEIS Frontend

A178523 The path length of the Fibonacci tree of order n.

%I A178523 #66 Apr 25 2025 21:12:12
%S A178523 0,0,2,6,16,36,76,152,294,554,1024,1864,3352,5968,10538,18478,32208,
%T A178523 55852,96420,165800,284110,485330,826752,1404816,2381616,4029216,
%U A178523 6803666,11468502,19300624,32433204,54426364,91216184,152691702,255313658,426460288,711634648
%N A178523 The path length of the Fibonacci tree of order n.
%C A178523 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 path length of a tree is the sum of the levels of all of its nodes.
%C A178523 This is also the number of configurations of n indistinguishable pairs placed on the vertices of the ladder graph P_2 X P_n such that all but one such pair are joined by an edge; equivalently the number of "(n-1)-domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young]. - _Donovan Young_, Oct 23 2018
%D A178523 Ralph P. Grimaldi, Properties of Fibonacci trees, In Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991); Congressus Numerantium 84 (1991), 21-32. - _Emeric Deutsch_, Sep 13 2010
%D A178523 D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
%H A178523 Muniru A Asiru, <a href="/A178523/b178523.txt">Table of n, a(n) for n = 0..4500</a>
%H A178523 Carlos Alirio Rico Acevedo, and Ana Paula Chaves, <a href="https://arxiv.org/abs/1903.07490">Double-Recurrence Fibonacci Numbers and Generalizations</a>, arXiv:1903.07490 [math.NT], 2019.
%H A178523 Y. Horibe, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/20-2/horibe.pdf">An entropy view of Fibonacci trees</a>, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
%H A178523 W. Kuszmaul, <a href="http://arxiv.org/abs/1509.08216">Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations</a>, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.
%H A178523 D. Young, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Young/young2.html">The Number of Domino Matchings in the Game of Memory</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
%H A178523 Donovan Young, <a href="https://arxiv.org/abs/1905.13165">Generating Functions for Domino Matchings in the 2 * k Game of Memory</a>, arXiv:1905.13165 [math.CO], 2019. Also in <a href="https://www.emis.de/journals/JIS/VOL22/Young/young13.html">J. Int. Seq.</a>, Vol. 22 (2019), Article 19.8.7.
%H A178523 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-3,1,1).
%F A178523 a(n) = 2 + (2/5)*(4n-9)*F(n) + (2/5)*(3n-5)*F(n-1), where F(n) = A000045(n) (Fibonacci numbers).
%F A178523 a(n) = 2*A006478(n+1).
%F A178523 a(n) = Sum_{k=0..n-1} k*A178522(n,k).
%F A178523 G.f.: 2*z^2/((1-z)*(1-z-z^2)^2).
%F A178523 From _Emeric Deutsch_, Sep 13 2010: (Start)
%F A178523 a(0)=a(1)=0, a(n) = a(n-1)+a(n-2)+2F(n+1)-2 if n>=2; here F(j)=A000045(j) are the Fibonacci numbers (see the Grimaldi reference, Eq. (**) on p. 23).
%F A178523 An explicit formula for a(n) is given in the Grimaldi reference (Theorem 2).
%F A178523 (End)
%F A178523 E.g.f.: 2*exp(x) + 2*exp(x/2)*(5*(4*x - 5)*cosh(sqrt(5)*x/2) + sqrt(5)*(10*x - 13)*sinh(sqrt(5)*x/2))/25. - _Stefano Spezia_, Dec 04 2023
%e A178523 a(2)=2 because the Fibonacci tree of order 2 is /\ with path length 1 + 1. - _Emeric Deutsch_, Sep 13 2010
%p A178523 with(combinat): a := proc (n) options operator, arrow: 2+((8/5)*n-18/5)*fibonacci(n)+((6/5)*n-2)*fibonacci(n-1) end proc: seq(a(n), n = 0 .. 35);
%p A178523 G := 2*z^2/((1-z)*(1-z-z^2)^2): Gser := series(G, z = 0, 40): seq(coeff(Gser, z, n), n = 0 .. 35);
%t A178523 Table[2 +2/5 (4n-9) Fibonacci[n] +2/5 (3n -5) Fibonacci[n-1], {n, 0, 40}] (* or *) LinearRecurrence[{3, -1, -3, 1, 1}, {0, 0, 2, 6, 16}, 40] (* _Harvey P. Dale_, Oct 02 2016 *)
%o A178523 (GAP) a:=[0,2];;  for n in [3..35] do a[n]:=a[n-1]+a[n-2]+ 2*Fibonacci(n +1) -2; od; Concatenation([0],a); # _Muniru A Asiru_, Oct 23 2018
%o A178523 (Magma) [2+(2/5)*(4*n-9)*Fibonacci(n)+(2/5)*(3*n-5)*Fibonacci(n-1): n in [0..40]]; // _Vincenzo Librandi_, Oct 24 2018
%o A178523 (PARI) vector(40, n, n--; (10+(8*n-18)*fibonacci(n)+(6*n-10)*fibonacci(n-1))/5) \\ _G. C. Greubel_, Jan 31 2019
%o A178523 (Sage) [(10+(8*n-18)*fibonacci(n)+(6*n-10)*fibonacci(n-1))/5 for n in range(40)] # _G. C. Greubel_, Jan 31 2019
%Y A178523 Cf. A000045, A006478, A178522, A002940, A067331.
%K A178523 nonn,easy
%O A178523 0,3
%A A178523 _Emeric Deutsch_, Jun 15 2010