

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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 n1 and whose right subtree is the Fibonacci tree of order n2; each of the Fibonacci trees of order 0 and 1 is defined as a single node.
Row n (n>=3) contains 2n3 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, AddisonWesley, 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, 168178.
B. E. Sagan, YN. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959969.


FORMULA

The Wiener polynomial w(n,t) of the Fibonacci tree of order n satisfies the recurrence relation w(n,t)=w(n1,t) + w(n2,t) + t*r(n1,t) + t*r(n2,t) + t^2*r(n1,t)*r(n2,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 := (1t*z+t*z^2)/((1z)*(1t*zt*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[n1]+w[n2]+t*r[n1]+t*r[n2]+t^2*r[n1]*r[n2])) end do: 2, 1; for n from 3 to 10 do seq(coeff(w[n], t, j), j = 1 .. 2*n3) end do; # yields sequence in triangular form


CROSSREFS

Cf. A178522, A180567
Sequence in context: A135366 A247248 A192017 * A051289 A090802 A129159
Adjacent sequences: A180563 A180564 A180565 * A180567 A180568 A180569


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Sep 14 2010


STATUS

approved



