

A178523


The path length of the Fibonacci tree of order n.


8



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

A Fibonacci tree of order n (n>=2) is a complete binary tree whose left subtree is the Fibonacci tree of order n1 and whose right subtree is the Fibonacci tree of order n2; 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 "(n1)domino" configurations in the game of memory played on a 2 X n rectangular array, see [Young].  Donovan Young, Oct 23 2018


REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, AddisonWesley, Reading, MA, 1998, p. 417.
R. P. Grimaldi, Properties of Fibonacci trees, Congr. Numer. 84 (1991), 2132. [Emeric Deutsch, Sep 13 2010]


LINKS

Muniru A Asiru, Table of n, a(n) for n = 0..4500
Carlos Alirio Rico Acevedo, Ana Paula Chaves, DoubleRecurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168178.
W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv preprint arXiv:1509.08216 [cs.DM], 20152017.
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).


FORMULA

a(n) = 2 + (2/5)*(4n9)*F(n) + (2/5)*(3n5)*F(n1), where F(n) = A000045(n) (Fibonacci numbers).
a(n) = 2*A006478(n+1).
a(n) = Sum_{k=0..n1} k*A178522(n,k).
G.f.: 2*z^2/((1z)*(1zz^2)^2).
From Emeric Deutsch, Sep 13 2010: (Start)
a(0)=a(1)=0, a(n) = a(n1)+a(n2)+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)


EXAMPLE

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


MAPLE

with(combinat): a := proc (n) options operator, arrow: 2+((8/5)*n18/5)*fibonacci(n)+((6/5)*n2)*fibonacci(n1) end proc: seq(a(n), n = 0 .. 35);
G := 2*z^2/((1z)*(1zz^2)^2): Gser := series(G, z = 0, 40): seq(coeff(Gser, z, n), n = 0 .. 35);


MATHEMATICA

Table[2 +2/5 (4n9) Fibonacci[n] +2/5 (3n 5) Fibonacci[n1], {n, 0, 40}] (* or *) LinearRecurrence[{3, 1, 3, 1, 1}, {0, 0, 2, 6, 16}, 40] (* Harvey P. Dale, Oct 02 2016 *)


PROG

(GAP) a:=[0, 2];; for n in [3..35] do a[n]:=a[n1]+a[n2]+ 2*Fibonacci(n +1) 2; od; Concatenation([0], a); # Muniru A Asiru, Oct 23 2018
(Magma) [2+(2/5)*(4*n9)*Fibonacci(n)+(2/5)*(3*n5)*Fibonacci(n1): n in [0..40]]; // Vincenzo Librandi, Oct 24 2018
(PARI) vector(40, n, n; (10+(8*n18)*fibonacci(n)+(6*n10)*fibonacci(n1))/5) \\ G. C. Greubel, Jan 31 2019
(Sage) [(10+(8*n18)*fibonacci(n)+(6*n10)*fibonacci(n1))/5 for n in range(40)] # G. C. Greubel, Jan 31 2019


CROSSREFS

Cf. A000045, A006478, A178522, A002940, A067331.
Sequence in context: A079990 A127902 A157136 * A270810 A227035 A257198
Adjacent sequences: A178520 A178521 A178522 * A178524 A178525 A178526


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Jun 15 2010


STATUS

approved



