A180567 The Wiener index of the Fibonacci tree of order n.

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

Offset: 0

Author

Emeric Deutsch, Sep 14 2010

Keywords

• nonn

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.

The Wiener index of a connected graph is the sum of the distances between all unordered pairs of nodes in the graph.

Examples

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

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

Programs

Maple

G := (1-t*z+t*z^2)/((1-z)*(1-t*z-t*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[n-1]+w[n-2]+t*r[n-1]+t*r[n-2]+t^2*r[n-1]*r[n-2])) end do: seq(subs(t = 1, diff(w[n], t)), n = 0 .. 27);

Formula

a(n) = Sum(k*A180566(n,k), k>=0).

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). 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^7-2*x^6-6*x^5+6*x^4+6*x^3-8*x^2+3*x-2)/((x+1)^2*(x^2-3*x+1)^2*(x^2+x-1)^2). [Colin Barker, Nov 17 2012]