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

%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