login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

REFERENCES

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

R. P. Grimaldi, Properties of Fibonacci trees, Congr. Numer. 84 (1991), 21-32. [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, 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.

Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,1,1).

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)

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

PROG

(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

(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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 03:08 EDT 2019. Contains 328211 sequences. (Running on oeis4.)