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

Author

Emeric Deutsch, Jan 18 2007

Keywords

• nonn
• tabf

Comments

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.

Examples

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

Links

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

Crossrefs

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

Programs

Maple

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

Formula

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