%I #16 Jan 21 2019 10:06:28
%S 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 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 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 Triangle read by rows: T(n,k) is the number of nodes of cost k in the Fibonacci tree of order n.
%C 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 The sum of the entries in row n is A001595(n) = 2F(n+1) - 1, where F(m)=A000045(m) (the Fibonacci numbers).
%C Sum(k*T(n,k), 0<=k<=n)=A178525(n).
%C _Daniel Forgues_, Aug 10 2012: (Start)
%C The falling diagonals are, starting from the rightmost one, with index 0:
%C d_0(i) = F(i-1), i >= 0;
%C d_j(i) = F(i+1), j >= 1, i >= 0.
%C Equivalently, as a single expression:
%C d_j(i) = F(i+1-2*0^j), j >= 0, i >= 0. (End)
%D D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
%H Y. Horibe, <a href="http://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 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 G.f.: (1-tz+tz^2)/[(1-z)(1-tz-t^2*z^2)].
%F 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 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 Triangle starts:
%e 1;
%e 1,0;
%e 1,1,1;
%e 1,1,2,1;
%e 1,1,2,3,2;
%e 1,1,2,3,5,3;
%e 1,1,2,3,5,8,5;
%p 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 Cf. A000045, A001595, A178525.
%K nonn,tabl
%O 0,9
%A _Emeric Deutsch_, Jun 16 2010