A192021 The Wiener index of the binomial tree of order n.

0, 1, 10, 68, 392, 2064, 10272, 49216, 229504, 1048832, 4719104, 20972544, 92276736, 402657280, 1744838656, 7516209152, 32212287488, 137439019008, 584115683328, 2473901424640, 10445360988160, 43980466159616, 184717955563520, 774056190148608, 3236962240561152

Offset: 0

Author

Emeric Deutsch, Jun 22 2011

Keywords

• nonn
• easy

Comments

The binomial trees b(k) of order k are ordered trees defined as follows: 1. b(0) consists of a single node. 2. For k>=1, b(k) is obtained from two copies of b(k-1) by linking them in such a way that the root of one is the leftmost child of the root of the other. See the Iyer & Reddy references.

References

• K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of Binomial trees and Fibonacci trees, Int'l. J. Math. Engin. with Comp., Accepted for publication, Sept. 2009.
• T. H. Cormen, C. E. Leiserson and R. L. Rivest: Introduction to Algorithms. MIT Press / McGraw-Hill (1990)

Links

• B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.
• K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, Wiener index of binomial trees and Fibonacci trees, arXiv:0910.4432 [cs.DM], 2009.
• Index entries for linear recurrences with constant coefficients, signature (10,-32,32).

Crossrefs

Cf. A192020.

Programs

Maple

a := proc(n) (n-1)*2^(2*n-1)+2^(n-1) end proc: seq(a(n), n = 0 .. 23);

Mathematica

LinearRecurrence[{10, -32, 32}, {0, 1, 10}, 23] (* Jean-François Alcover, Sep 23 2017 *)

Formula

a(n) = Sum_{k>=1} k*A192020(n,k).

From Colin Barker, Jul 07 2012: (Start)

a(n) = 2^(n-1)*(1+2^n*(n-1)).

a(n) = 10*a(n-1) - 32*a(n-2) + 32*a(n-3).

G.f.: x/((1-2*x)*(1-4*x)^2). (End)

Extensions

Initial 0 in the sample values which is Wiener index of singleton tree b(0), and consequent amendments to formulas. - Kevin Ryde, Sep 12 2019