|
| |
|
|
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
|
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
|
|
|
|
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) = Sum_{k=0..n-1} k*A178522(n,k).
G.f.: 2*z^2/((1-z)*(1-z-z^2)^2).
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
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
