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

0, 0, 2, 6, 16, 36, 76, 152, 294, 554, 1024, 1864, 3352, 5968, 10538, 18478, 32208, 55852, 96420, 165800, 284110, 485330, 826752, 1404816, 2381616, 4029216, 6803666, 11468502, 19300624, 32433204, 54426364, 91216184, 152691702, 255313658, 426460288, 711634648

Offset: 0

Author

Emeric Deutsch, Jun 15 2010

Keywords

• nonn
• easy

Comments

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.

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

Examples

			a(2)=2 because the Fibonacci tree of order 2 is /\ with path length 1 + 1. - _Emeric Deutsch_, Sep 13 2010
		

References

• 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. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Links

• Muniru A Asiru, Table of n, a(n) for n = 0..4500
• Carlos Alirio Rico Acevedo, and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
• Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
• W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 2015-2017.
• D. Young, The Number of Domino Matchings in the Game of Memory, Journal of Integer Sequences, Vol. 21 (2018), Article 18.8.1.
• Donovan Young, Generating Functions for Domino Matchings in the 2 * k Game of Memory, arXiv:1905.13165 [math.CO], 2019. Also in J. Int. Seq., Vol. 22 (2019), Article 19.8.7.
• Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

Crossrefs

Cf. A000045, A006478, A178522, A002940, A067331.

Programs

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

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

Maple

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);
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);

Mathematica

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

PARI

vector(40, n, n--; (10+(8*n-18)*fibonacci(n)+(6*n-10)*fibonacci(n-1))/5) \\ G. C. Greubel, Jan 31 2019

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

Formula

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

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

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

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

From Emeric Deutsch, Sep 13 2010: (Start)

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

An explicit formula for a(n) is given in the Grimaldi reference (Theorem 2).

(End)

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