login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
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. 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)*(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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 05:56 EST 2022. Contains 358512 sequences. (Running on oeis4.)