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

1, 1, 2, 4, 1, 8, 5, 1, 16, 17, 8, 1, 32, 49, 38, 12, 1, 64, 129, 141, 77, 17, 1, 128, 321, 453, 361, 143, 23, 1, 256, 769, 1326, 1399, 834, 247, 30, 1, 512, 1793, 3640, 4776, 3869, 1765, 402, 38, 1, 1024, 4097, 9539, 14911, 15353, 9722, 3469, 623, 47, 1, 2048, 9217

Offset: 0

Author

Emeric Deutsch, Jan 18 2007

Keywords

• nonn
• tabf

Comments

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.

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) = A011782(n).

T(n,1) = A000337(n-2).

Sum_{k>=0} k*T(n,k) = binomial(2n-1, n-3) = A003516(n-1) for n >= 3.

The distribution of the statistic "number of jumps" is given in A091894. The average jump distance in all ordered trees with n edges is 2 - 5/(n+2) (i.e., about 2 levels for n large). The Krandick reference considers jump-length for full binary trees.

Also the number of Dyck n-paths with k valleys at height >= 1. - David Scambler, Sep 01 2011

Triangle T(n,k), with zeros omitted, given by (1,1,0,1,0,1,0,1,0,1,0,1,...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,1,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 06 2012

Examples

			Triangle starts:
   1;
   1;
   2;
   4,  1;
   8,  5,  1;
  16, 17,  8,  1;
  32, 49, 38, 12, 1;
Triangle (1,1,0,1,0,1,0,1,0,1, ...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,...) begins:
   1;
   1,   0;
   2,   0,   0;
   4,   1,   0,  0;
   8,   5,   1,  0,  0;
  16,  17,   8,  1,  0, 0;
  32,  49,  38, 12,  1, 0, 0;
  64, 129, 141, 77, 17, 1, 0, 0; ... - _Philippe Deléham_, Feb 06 2012
		

Links

• E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see Table 2).
• FindStat - Combinatorial Statistic Finder, The number of valleys not on the x-axis of a Dyck path.
• W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Crossrefs

Cf. A000108, A000337, A003516, A011782, A091894.

Programs

Maple

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

Mathematica

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

Maxima

T(n,m):=if n=0 and m=0 then 1 else if n=0 then 0 else sum(k*binomial(n,m+k)*binomial(n-k-1,m),k,0,n-m)/(n); /* Vladimir Kruchinin, Oct 29 2020 */

Formula

G.f.: G=G(t,z) satisfies (1 - t - 2*z + t*z)*G^2 - (1 - 2*t - z + t*z)*G - t = 0.

T(n,m) = Sum_{k=0..n-m} k*C(n,m+k)*C(n-k-1,m)/n, n>0, T(0,0)=1. - Vladimir Kruchinin, Oct 29 2020