cp's OEIS Frontend

A178526 Triangle read by rows: T(n,k) is the number of nodes of cost k in the Fibonacci tree of order n.

%I A178526 #18 Jan 05 2025 19:51:39
%S A178526 1,1,0,1,1,1,1,1,2,1,1,1,2,3,2,1,1,2,3,5,3,1,1,2,3,5,8,5,1,1,2,3,5,8,
%T A178526 13,8,1,1,2,3,5,8,13,21,13,1,1,2,3,5,8,13,21,34,21,1,1,2,3,5,8,13,21,
%U A178526 34,55,34,1,1,2,3,5,8,13,21,34,55,89,55,1,1,2,3,5,8,13,21,34,55,89,144,89
%N A178526 Triangle read by rows: T(n,k) is the number of nodes of cost k in the Fibonacci tree of order n.
%C A178526 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. In a Fibonacci tree the cost of a left (right) edge is defined to be 1 (2). The cost of a node of a Fibonacci tree is defined to be the sum of the costs of the edges that form the path from the root to this node.
%C A178526 The sum of the entries in row n is A001595(n) = 2F(n+1) - 1, where F(m)=A000045(m) (the Fibonacci numbers).
%C A178526 Sum(k*T(n,k), 0<=k<=n)=A178525(n).
%C A178526 _Daniel Forgues_, Aug 10 2012: (Start)
%C A178526 The falling diagonals are, starting from the rightmost one, with index 0:
%C A178526   d_0(i) = F(i-1), i >= 0;
%C A178526   d_j(i) = F(i+1), j >= 1, i >= 0.
%C A178526 Equivalently, as a single expression:
%C A178526   d_j(i) = F(i+1-2*0^j), j >= 0, i >= 0. (End)
%D A178526 D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
%H A178526 Y. Horibe, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/20-2/horibe.pdf">An entropy view of Fibonacci trees</a>, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
%F A178526 T(n,k)=F(k+1) if k<n; T(n,n)=F(n-1); T(n,k)=0 if k>n; here F(m)=A000045(m) (the Fibonacci numbers).
%F A178526 G.f.: (1-tz+tz^2)/[(1-z)(1-tz-t^2*z^2)].
%F A178526 The enumerating polynomials P[n] of row n are given by P[0]=1, P[n]=P[n-1]+F(n-1)*(t^{n-1}+t^n) for n>=1, where F(m)=A000045(m) (the Fibonacci numbers).
%e A178526 In the Fibonacci tree /\ of order 2 we have a node of cost 0 (the root), a node of cost 1 (the left leaf), and a node of cost 2 (the right leaf).
%e A178526 Triangle starts:
%e A178526 1;
%e A178526 1,0;
%e A178526 1,1,1;
%e A178526 1,1,2,1;
%e A178526 1,1,2,3,2;
%e A178526 1,1,2,3,5,3;
%e A178526 1,1,2,3,5,8,5;
%p A178526 with(combinat): T := proc (n, k) if k < n then fibonacci(k+1) elif k = n then fibonacci(n-1) else 0 end if end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form
%Y A178526 Cf. A000045, A001595, A178525.
%K A178526 nonn,tabl
%O A178526 0,9
%A A178526 _Emeric Deutsch_, Jun 16 2010