A192021 -id:A192021 - cp's OEIS frontend

A367076 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). T(n,k) = -Sum_{i=0..k} A365968(n,i).

0, 1, 0, 3, 4, 3, 0, 6, 10, 12, 12, 12, 10, 6, 0, 10, 18, 24, 28, 32, 34, 34, 32, 34, 34, 32, 28, 24, 18, 10, 0, 15, 28, 39, 48, 57, 64, 69, 72, 79, 84, 87, 88, 89, 88, 85, 80, 85, 88, 89, 88, 87, 84, 79, 72, 69, 64, 57, 48, 39, 28, 15, 0, 21, 40, 57, 72, 87

Offset: 0

John Tyler Rascoe, Nov 05 2023

			Triangle begins:
    k=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
n=0:  0;
n=1:  1,  0;
n=2:  3,  4,  3,  0;
n=3:  6, 10, 12, 12, 12, 10,  6,  0;
n=4; 10, 18, 24, 28, 32, 34, 34, 32, 34, 34, 32, 28, 24, 18, 10,  0;

John Tyler Rascoe, Rows n = 0..12, flattened
Wikipedia, Blancmange curve.
Index entries for sequences related to binary expansion of n

Cf. A000217 (column k=0), A028552 (column k=1), A192021 (row sums).

Cf. A004074, A249071, A274575, A277914, A296062, A365968.

nmax=10; row[n_]:=Join[CoefficientList[Series[1/(1-x)*Sum[ i/(1+x^2^(i-1))*Product[1+x^2^j,{j,0,i-2}],{i,n}],{x,0,2^n-1}],x],{0}]; Array[row,6,0] (* Stefano Spezia, Dec 23 2023 *)

def row_gen(n):
    x = 0
    for k in range(2**n):
        b = bin(k)[2:].zfill(n)
        x += sum((-1)**(int(b[n-i])+1)*i for i in range(1,n+1))
        yield(-x)
def A367076_row_n(n): return(list(row_gen(n)))

T(n,k) = Sum_{i=0..n} abs(k + 1 - (2^i) * round((k+1)/2^i)) * i.

G.f. for n-th row: 1/(1-x) * Sum_{i=1..n} (i/(1+x^2^(i-1)) * Product_{j=0..i-2} 1 + x^2^j).

A192020 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).

Original entry on oeis.org

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, 114, 225, 344, 418, 388, 270, 136, 47, 10, 1, 127, 240, 516, 908, 1331, 1568, 1464, 1064, 589, 240, 68, 12, 1, 255, 494, 1123, 2180, 3663, 5138, 5931, 5560, 4181, 2482, 1137, 388, 93, 14, 1

Offset: 0

Emeric Deutsch, Jun 22 2011

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.
Row n contains 2n-1 entries.
Kevin Ryde, Sep 14 2019: (Start)
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).
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).
(End)

			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.
Triangle starts:
   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;

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

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.

Cf. A000225, A005803, A192021.

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

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 *)

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

T(n,1) = A000225(n) = 2^n - 1.
T(n,2) = A005803(n+1) = 2^(n+1) - 2*n - 2.
Sum_{k>=1} k*T(n,k) = A192021(n) (the Wiener indices).
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).
T(n,k) = Sum_{j=1..n} 2^(n-j)*binomial(2*j-2, k-1).
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

cp's OEIS Frontend

A367076 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). T(n,k) = -Sum_{i=0..k} A365968(n,i).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula