login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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.
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.
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]
EXAMPLE
a(2)=4 because in the tree /\ we have 3 distances: 1, 1, and 2.
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);
CROSSREFS
Sequence in context: A081103 A243325 A005777 * A152392 A001563 A094304
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Sep 14 2010
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 3 11:33 EST 2024. Contains 370511 sequences. (Running on oeis4.)