login
The path length of the Fibonacci tree of order n.
8

%I #61 Dec 08 2023 09:57:57

%S 0,0,2,6,16,36,76,152,294,554,1024,1864,3352,5968,10538,18478,32208,

%T 55852,96420,165800,284110,485330,826752,1404816,2381616,4029216,

%U 6803666,11468502,19300624,32433204,54426364,91216184,152691702,255313658,426460288,711634648

%N The path length of the Fibonacci tree of order n.

%C 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 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 Ralph P. Grimaldi, Properties of Fibonacci trees, In Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph The­ory, and Computing (Baton Rouge, LA, 1991); Congressus Numerantium 84 (1991), 21-32. [_Emeric Deutsch_, Sep 13 2010]

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

%H Muniru A Asiru, <a href="/A178523/b178523.txt">Table of n, a(n) for n = 0..4500</a>

%H 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 Y. Horibe, <a href="http://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 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 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 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 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-3,1,1).

%F a(n) = 2 + (2/5)*(4n-9)*F(n) + (2/5)*(3n-5)*F(n-1), where F(n) = A000045(n) (Fibonacci numbers).

%F a(n) = 2*A006478(n+1).

%F a(n) = Sum_{k=0..n-1} k*A178522(n,k).

%F G.f.: 2*z^2/((1-z)*(1-z-z^2)^2).

%F From _Emeric Deutsch_, Sep 13 2010: (Start)

%F 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 An explicit formula for a(n) is given in the Grimaldi reference (Theorem 2).

%F (End)

%F 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 a(2)=2 because the Fibonacci tree of order 2 is /\ with path length 1 + 1. - _Emeric Deutsch_, Sep 13 2010

%p 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 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 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 (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 (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 (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 (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 Cf. A000045, A006478, A178522, A002940, A067331.

%K nonn,easy

%O 0,3

%A _Emeric Deutsch_, Jun 15 2010