login
Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k valleys.
0

%I #9 Oct 14 2020 11:05:37

%S 2,5,1,14,7,1,42,36,11,1,132,165,80,16,1,429,715,484,155,22,1,1430,

%T 3003,2639,1183,273,29,1,4862,12376,13468,7840,2554,448,37,1,16796,

%U 50388,65688,47328,20124,5031,696,46,1,58786,203490,310080,267444,141219

%N Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k valleys.

%C A Schroeder path of length 2n is a lattice path starting from (0,0), ending at (2n,0), consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis (Schroeder paths are counted by the large Schroeder numbers (A006318)). Also number of Schroeder paths of length 2n and having k UU's. Also number of Schroeder paths of length 2n and having k peaks at height >1,

%F G.f.=G=G(t, z) satisfies z(t+z-tz)G^2-(1-2z+tz)G+1=0.

%F T(n,m) = Sum_{k=0..n-m} (k+1)*C(n-k,m-1)*C(2*n-m-k+1,n+1)/(n-k), m>1, T(n,1) = 1/(n+1)*binomial(2*n+2,n). - _Vladimir Kruchinin_, Oct 14 2020

%e T(3,1)=7 because we have HU(DU)D, U(DU)DH, U(DU)HD, UH(DU)D, U(DU)UDD,

%e UUD(DU)D and UU(DU)DD, the valleys being shown between parentheses.

%e Triangle begins:

%e 2;

%e 5,1;

%e 14,7,1;

%e 42,36,11,1;

%e 132,165,80,16,1;

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

%o (Maxima)

%o T(n,m):=if n=0 or m=0 then 0 else if m=1 then 1/(n+1)*binomial(2*n+2,n) else sum(((k+1)*binomial(n-k,m-1)*binomial(2*n-m-k+1,n+1))/(n-k),k,0,n-m); /* _Vladimir Kruchinin_, Oct 14 2020 */

%Y Cf. A006318, A000108, A003516.

%K nonn,tabl

%O 1,1

%A _Emeric Deutsch_, Dec 20 2004