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

%I A127532 #9 Nov 15 2019 01:22:11
%S A127532 1,2,5,12,2,29,9,4,70,32,22,8,169,102,86,56,16,408,306,296,244,144,32,
%T A127532 985,883,949,901,712,368,64,2378,2480,2908,3056,2822,2096,928,128,
%U A127532 5741,6828,8633,9830,10074,8976,6144,2304,256,13860,18514,25032,30482,33792
%N 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).
%C A127532 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.
%C A127532 Rows 0 and 1 have one term each; row n (n >= 2) has n-1 terms.
%C A127532 Row sums are the Catalan numbers (A000108).
%C A127532 T(n,0) = A000129(n+1) (the Pell numbers).
%C A127532 T(n,1) = A074084(n).
%C A127532 Sum_{k>=0} k*T(n,k) = binomial(2n+1, n-3) + binomial(2n, n-3) = A127533(n).
%C A127532 The distribution of the statistic "number of jumps" is given in A127530.
%C A127532 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.
%H A127532 W. Krandick, <a href="http://dx.doi.org/10.1016/j.cam.2003.08.018">Trees and jumps and real roots</a>, J. Computational and Applied Math., 162, 2004, 51-55.
%F A127532 G.f.: G = G(t,z) is given by (1 - t - 2z + 2tz - z^2)*G^2 - (1 - 2t + 2tz)*G - t = 0.
%e A127532 Triangle starts:
%e A127532    1;
%e A127532    2;
%e A127532    5;
%e A127532   12,  2;
%e A127532   29,  9,  4;
%e A127532   70, 32, 22,  8;
%p A127532 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
%Y A127532 Cf. A000108, A000129, A074084, A127530, A127533.
%K A127532 nonn,tabf
%O A127532 0,2
%A A127532 _Emeric Deutsch_, Jan 18 2007