OFFSET
0,2
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.
LINKS
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.
FORMULA
G.f.: G = G(t,z) is given by (1 - t - 2z + 2tz - z^2)*G^2 - (1 - 2t + 2tz)*G - t = 0.
EXAMPLE
Triangle starts:
1;
2;
5;
12, 2;
29, 9, 4;
70, 32, 22, 8;
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
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jan 18 2007
STATUS
approved