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,1

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).

References

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

Links

Table of n, a(n) for n=2..67.

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.

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).

Example

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;

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

Crossrefs

Cf. A178522, A180567

Sequence in context: A135366 A247248 A192017 * A051289 A134308 A090802

Adjacent sequences: A180563 A180564 A180565 * A180567 A180568 A180569

Keyword

nonn,tabf

Author

Emeric Deutsch, Sep 14 2010

Status

approved