A180566 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the Fibonacci tree of order n (entries in row n are the coefficients of the corresponding Wiener polynomial).

2, 1, 4, 4, 2, 8, 10, 8, 6, 4, 14, 19, 20, 18, 18, 12, 4, 24, 34, 40, 44, 48, 46, 40, 20, 4, 40, 58, 72, 88, 106, 114, 122, 112, 76, 28, 4, 66, 97, 124, 160, 208, 242, 284, 310, 308, 244, 128, 36, 4, 108, 160, 208, 276, 376, 466, 576, 686, 782, 812, 720, 472, 196, 44, 4, 176

Offset: 2

Author

Emeric Deutsch, Sep 14 2010

Keywords

• nonn
• tabf

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.

Row n (n>=3) contains 2n-3 entries.

Sum of entries of row n is (F(n+1) - 1)(2F(n+1) - 1), where F(j)=A000045(j) are the Fibonacci numbers.

T(n,1) = 2*F(n+1)-2 = number of edges in the Fibonacci tree of order n.

Sum(k*T(n,k), k>=0) = A180567 (the Wiener index of the Fibonacci tree of order n).

Examples

			T(2,2)=1 because in the Fibonacci tree of order 2, namely /\, there is only 1 pair of nodes at distance 2 (the two leaves).
Triangle starts:
2,1;
4,4,2;
8,10,8,6,4;
14,19,20,18,18,12,4;
		

References

• D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.

Links

• Y. Horibe, An entropy view of Fibonacci trees, Fibonacci Quarterly, 20, No. 2, 1982, 168-178.
• B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.

Crossrefs

Cf. A178522, A180567

Programs

Maple

G := (1-t*z+t*z^2)/((1-z)*(1-t*z-t*z^2)): Gser := simplify(series(G, z = 0, 25)): for n from 0 to 20 do r[n] := sort(coeff(Gser, z, n)) end do: w[0] := 0: w[1] := 0: for n from 2 to 15 do w[n] := sort(expand(w[n-1]+w[n-2]+t*r[n-1]+t*r[n-2]+t^2*r[n-1]*r[n-2])) end do: 2, 1; for n from 3 to 10 do seq(coeff(w[n], t, j), j = 1 .. 2*n-3) end do; # yields sequence in triangular form

Formula

The Wiener polynomial w(n,t) of the Fibonacci tree of order n satisfies the recurrence relation w(n,t)=w(n-1,t) + w(n-2,t) + t*r(n-1,t) + t*r(n-2,t) + t^2*r(n-1,t)*r(n-2,t), w(0,t)=w(1,t)=0, where r(n,t) is the generating polynomial of the nodes of the Fibonacci tree of order n with respect to the level of the nodes (for example, 1+2t for the tree /\; see A178522 and the Maple program).