

A180567


The Wiener index of the Fibonacci tree of order n.


1



0, 0, 4, 18, 96, 374, 1380, 4696, 15336, 48318, 148448, 446890, 1324104, 3872656, 11206764, 32143818, 91509120, 258855006, 728211180, 2038815272, 5684262480, 15789141750, 43712852544, 120663667538, 332191809936, 912339490464
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


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.
The Wiener index of a connected graph is the sum of the distances between all unordered pairs of nodes in the graph.


REFERENCES

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


LINKS



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). The Wiener index is the derivative of w(n,t) with respect to t, evaluated at t=1 (see the Maple program).
Empirical G.f.: 2*x^2*(x^72*x^66*x^5+6*x^4+6*x^38*x^2+3*x2)/((x+1)^2*(x^23*x+1)^2*(x^2+x1)^2). [Colin Barker, Nov 17 2012]


EXAMPLE

a(2)=4 because in the tree /\ we have 3 distances: 1, 1, and 2.


MAPLE

G := (1t*z+t*z^2)/((1z)*(1t*zt*z^2)): Gser := simplify(series(G, z = 0, 38)): for n from 0 to 35 do r[n] := sort(coeff(Gser, z, n)) end do: w[0] := 0: w[1] := 0: for n from 2 to 30 do w[n] := sort(expand(w[n1]+w[n2]+t*r[n1]+t*r[n2]+t^2*r[n1]*r[n2])) end do: seq(subs(t = 1, diff(w[n], t)), n = 0 .. 27);


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



