|
%I #34 Apr 07 2020 23:12:53
%S 1,3,2,1,7,8,8,4,1,15,22,31,28,17,6,1,31,52,90,112,104,68,30,8,1,63,
%T 114,225,344,418,388,270,136,47,10,1,127,240,516,908,1331,1568,1464,
%U 1064,589,240,68,12,1,255,494,1123,2180,3663,5138,5931,5560,4181,2482,1137,388,93,14,1
%N Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the binomial tree of order n (1 <= k <= 2n-1; entries in row n are the coefficients of the corresponding Wiener polynomial).
%C The binomial trees b(k) of order k are ordered trees defined as follows:
%C 1. b(0) consists of a single node.
%C 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.
%C Row n contains 2n-1 entries.
%C _Kevin Ryde_, Sep 14 2019: (Start)
%C In the formulas below, the generating function for number of vertices at depth is r(n,t) = (t+1)^n = Sum_{i=0..n} binomial(n,i)*t^i. The w(n,t) recurrence applied repeatedly is a sum of those, and from which the rational function for w(n,t).
%C T(n,k) as sum over j follows from which binomials are put at which indices in the g.f. Or the direct interpretation is to number vertices v=0 to 2^n-1 inclusive with parent(v) = A129760(v) in the usual way, then suppose a pair of vertices u,v have their highest differing bit at position j, where j=1 as the least significant bit. One of u or v has a 1-bit at j. To be distance k apart requires k-1 further 1-bits among the bits below j in u and v, hence binomial(2(j-1),k-1). The bits above j are the same in u and v and can be any 2^(n-j) (those bits and 0's below are the common ancestor of u,v).
%C (End)
%D 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.
%D T. H. Cormen, C. E. Leiserson and R. L. Rivest: Introduction to Algorithms. MIT Press / McGraw-Hill (1990).
%H B. E. Sagan, Y-N. Yeh and P. Zhang, <a href="http://dx.doi.org/10.1002/(SICI)1097-461X(1996)60:5<959::AID-QUA2>3.0.CO;2-W">The Wiener Polynomial of a Graph</a>, Internat. J. of Quantum Chem., 60, 1996, 959-969.
%H K. Viswanathan Iyer and K. R. Udaya Kumar Reddy, <a href="http://arxiv.org/abs/0910.4432">Wiener index of binomial trees and Fibonacci trees</a>, arXiv:0910.4432 [cs.DM], 2009.
%F T(n,1) = A000225(n) = 2^n - 1.
%F T(n,2) = A005803(n+1) = 2^(n+1) - 2*n - 2.
%F Sum_{k>=1} k*T(n,k) = A192021(n) (the Wiener indices).
%F The Wiener polynomial w(n,t) of the binomial tree of order n satisfies the recurrence relation w(n,t) = 2*w(n-1,t) + t*(r(n-1,t))^2, w(0,t)=0, where r(n,t) is the generating polynomial of the nodes of the binomial tree b(n) with respect to the level of the nodes (for example, r(1,t) = 1 + t for the one-edge tree b(1)= | ; see the Maple program).
%F T(n,k) = Sum_{j=1..n} 2^(n-j)*binomial(2*j-2, k-1).
%F w(n,t) = Sum_{i=0..n-1} 2^(n-1-i)*t*(t+1)^(2i) = t * ((t+1)^(2n) - 2^n)/((t+1)^2 - 2). - _Kevin Ryde_, Sep 13 2019
%e T(2,1)=3, T(2,2)=2, T(2,3)=1 because the binomial tree b(2) is basically the path tree A-B-R-C and we have 3 (AB, BR, RC), 2 (AR, BC), and 1 (AC) pairs of nodes at distances 1, 2, and 3, respectively.
%e Triangle starts:
%e 1;
%e 3, 2, 1;
%e 7, 8, 8, 4, 1;
%e 15, 22, 31, 28, 17, 6, 1;
%e 31, 52, 90, 112, 104, 68, 30, 8, 1;
%p G := 1/(1-z-t*z): Gser := simplify(series(G, z = 0, 11)): for n from 0 to 8 do r[n] := sort(coeff(Gser, z, n)) end do: w[0] := 0: for n to 8 do w[n] := sort(expand(2*w[n-1]+t*r[n-1]^2)) end do: for n to 8 do seq(coeff(w[n], t, k), k = 1 .. 2*n-1) end do; # yields sequence in triangular form
%t max = 8; g = 1/(1 - z - t*z); r = CoefficientList[ Series[g, {z, 0, max}], z]; w[0] = 0; w[n_] := w[n] = 2 w[n-1] + t*r[[n]]^2; Flatten[ Table[ Drop[ CoefficientList[ w[n], t], 1], {n, 1, max}]] (* _Jean-François Alcover_, Oct 06 2011, after Maple *)
%o (PARI) a(n) = my(s=sqrtint(n),r=n-s^2); sum(i=0,s, 2^(s-i)*binomial(2*i,r)); \\ _Kevin Ryde_, Sep 13 2019
%Y Cf. A000225, A005803, A192021.
%K nonn,tabf
%O 0,2
%A _Emeric Deutsch_, Jun 22 2011
|
