A127530 Triangle read by rows: T(n,k) is the number of binary trees with n edges and k jumps (n >= 0, 0 <= k <= max(0,ceiling(n/2)-1) ).

1, 2, 5, 12, 2, 29, 13, 70, 60, 2, 169, 235, 25, 408, 836, 184, 2, 985, 2790, 1046, 41, 2378, 8896, 5080, 440, 2, 5741, 27410, 22164, 3410, 61, 13860, 82230, 89440, 21580, 900, 2, 33461, 241467, 340058, 118714, 9115, 85, 80782, 696732, 1233562, 588952

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 Krandick reference considers the statistic "number of jumps" for full binary trees.

Row 0 has one term, row n (n >= 1) has ceiling(n/2) terms.

Examples

			Triangle starts:
    1;
    2;
    5;
   12,   2;
   29,  13;
   70,  60,  2;
  169, 235, 25;
		

Links

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

Crossrefs

Cf. A000108, A000129, A127531.

Programs

Maple

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

Mathematica

n = 13; g[t_, z_] := (-z^2 - 2z + z^2*t + 1 - Sqrt[z^4 + 4z^3 - 2z^4*t + 2z^2 - 4z^3*t - 4z + z^4*t^2 - 2z^2*t + 1])/2/t/z^2; Flatten[ CoefficientList[#1, t] & /@ CoefficientList[Simplify[Series[g[t, z], {z, 0, n}]], z]] (* Jean-François Alcover, Jul 22 2011, after g.f. *)

Formula

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

Row sums are the Catalan numbers (A000108(n+1)).

T(n,0) = A000129(n+1) (the Pell numbers).

Sum_{k>=0} k*T(n,k) = binomial(2*n, n-2) - binomial(2n-2,n-2) = A127531(n).