A127533 -id:A127533 - cp's OEIS frontend

A127532 Triangle read by rows: T(n,k) is the number of binary trees with n edges and jump-length equal to k (n >= 0, 0 <= k <= n-2).

1, 2, 5, 12, 2, 29, 9, 4, 70, 32, 22, 8, 169, 102, 86, 56, 16, 408, 306, 296, 244, 144, 32, 985, 883, 949, 901, 712, 368, 64, 2378, 2480, 2908, 3056, 2822, 2096, 928, 128, 5741, 6828, 8633, 9830, 10074, 8976, 6144, 2304, 256, 13860, 18514, 25032, 30482, 33792

Offset: 0

Emeric Deutsch, Jan 18 2007

In the preorder traversal of a binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given binary tree is called the jump-length.
Rows 0 and 1 have one term each; row n (n >= 2) has n-1 terms.
Row sums are the Catalan numbers (A000108).
T(n,0) = A000129(n+1) (the Pell numbers).
T(n,1) = A074084(n).
Sum_{k>=0} k*T(n,k) = binomial(2n+1, n-3) + binomial(2n, n-3) = A127533(n).
The distribution of the statistic "number of jumps" is given in A127530.
The average jump distance in all binary trees with n edges is 2n(3n+5)(2n-1)/((n+3)(n+4)(3n+1)) (i.e., about 4 levels when n is large). The Krandick reference considers jump-length for full binary trees.

			Triangle starts:
   1;
   2;
   5;
  12,  2;
  29,  9,  4;
  70, 32, 22,  8;

W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Cf. A000108, A000129, A074084, A127530, A127533.

G:=(-1+2*t-2*t*z-sqrt(1-4*t*z+4*t^2*z^2-4*t*z^2))/2/(z^2-1+t-2*t*z+2*z): Gser:=simplify(series(G,z=0,17)): for n from 0 to 12 do P[n]:=sort(coeff(Gser,z,n)) od: 1;2;for n from 2 to 12 do seq(coeff(P[n],t,j),j=0..n-2) od; # yields sequence in triangular form

G.f.: G = G(t,z) is given by (1 - t - 2z + 2tz - z^2)*G^2 - (1 - 2t + 2tz)*G - t = 0.

A127536 Sum of jump-lengths of all even trees with 2n edges.

Original entry on oeis.org

0, 1, 10, 77, 546, 3740, 25194, 168245, 1118260, 7413705, 49085400, 324794316, 2148789800, 14217578856, 94096891658, 622997471685, 4126520887720, 27345271410275, 181295437422330, 1202538435463365, 7980245606038650

Offset: 1

Emeric Deutsch, Jan 19 2007

nonn

An even tree is an ordered tree in which each vertex has an even outdegree. In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given ordered tree is called the jump-length.

The Krandick reference considers jumps and jump-length only in full binary trees.

W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Cf. A127535, A127533.

seq((n-1)*(2*n-1)*binomial(3*n,n)/3/(n+1)/(2*n+1),n=1..25);

Table[(n - 1) (2 n - 1) Binomial[3 n, n]/3/(n + 1)/(2*n + 1), {n, 30}] (* Wesley Ivan Hurt, Aug 04 2025 *)

a(n) = (n-1)(2n-1)C(3n,n)/[3(n+1)/(2n+1)].
a(n) = Sum_{k=0..n-1} k*A127535(n,k).
D-finite with recurrence 2*(n-2)*(2*n+1)*(2*n-3)*(n+1)*a(n) -3*(n-1)*(3*n-1)*(2*n-1)*(3*n-2)*a(n-1)=0. - R. J. Mathar, Jul 26 2022

cp's OEIS Frontend

A127532 Triangle read by rows: T(n,k) is the number of binary trees with n edges and jump-length equal to k (n >= 0, 0 <= k <= n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula