|
%I #42 Nov 15 2020 12:58:59
%S 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,
%T 453,361,143,23,1,256,769,1326,1399,834,247,30,1,512,1793,3640,4776,
%U 3869,1765,402,38,1,1024,4097,9539,14911,15353,9722,3469,623,47,1,2048,9217
%N 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).
%C 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.
%C Rows 0 and 1 have one term each; row n (n >= 2) has n-1 terms.
%C Row sums are the Catalan numbers (A000108).
%C T(n,0) = A011782(n).
%C T(n,1) = A000337(n-2).
%C Sum_{k>=0} k*T(n,k) = binomial(2n-1, n-3) = A003516(n-1) for n >= 3.
%C 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.
%C Also the number of Dyck n-paths with k valleys at height >= 1. - _David Scambler_, Sep 01 2011
%C 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
%H E. Deutsch, <a href="http://dx.doi.org/10.1016/S0012-365X(98)00371-9">Dyck path enumeration</a>, Discrete Math., 204, 1999, 167-202 (see Table 2).
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000052">The number of valleys not on the x-axis of a Dyck path.</a>
%H 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 G.f.: G=G(t,z) satisfies (1 - t - 2*z + t*z)*G^2 - (1 - 2*t - z + t*z)*G - t = 0.
%F 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
%e Triangle starts:
%e 1;
%e 1;
%e 2;
%e 4, 1;
%e 8, 5, 1;
%e 16, 17, 8, 1;
%e 32, 49, 38, 12, 1;
%e 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:
%e 1;
%e 1, 0;
%e 2, 0, 0;
%e 4, 1, 0, 0;
%e 8, 5, 1, 0, 0;
%e 16, 17, 8, 1, 0, 0;
%e 32, 49, 38, 12, 1, 0, 0;
%e 64, 129, 141, 77, 17, 1, 0, 0; ... - _Philippe Deléham_, Feb 06 2012
%p 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
%t 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. *)
%o (Maxima)
%o 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 */
%Y Cf. A000108, A000337, A003516, A011782, A091894.
%K nonn,tabf
%O 0,3
%A _Emeric Deutsch_, Jan 18 2007
|
