login
Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n having exactly k down steps hitting the x-axis.
4

%I #13 Apr 22 2015 16:21:36

%S 1,1,1,1,4,1,1,13,7,1,1,44,34,10,1,1,165,150,64,13,1,1,680,659,346,

%T 103,16,1,1,3001,2973,1753,659,151,19,1,1,13880,13844,8716,3798,1116,

%U 208,22,1,1,66345,66300,43384,20798,7226,1744,274,25,1,1,324908,324853,217804

%N Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n having exactly k down steps hitting the x-axis.

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

%H Alois P. Heinz, <a href="/A101275/b101275.txt">Rows n = 0..140, flattened</a>

%F G.f.: 2/[2-2z-t+tz+t*sqrt(1-6z+z^2)].

%F 1/(1-x-xy/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-.... (continued fraction). - _Paul Barry_, Feb 01 2009

%F T(n,k)= k*Sum_{m=0..n-k}(Sum_{i=0..m}(C(m+k,i)*C(2*m+k-i-1,m+k-1))*C(n-m,k))/(m+k)), T(n,0)=1. - _Vladimir Kruchinin_, Apr 20 2015

%e Example. T(2,1)=4 because we have UHD, UUDD, HUD and UDH.

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 4, 1;

%e 1, 13, 7, 1;

%e 1, 44, 34, 10, 1;

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

%o (Maxima)

%o T(n,k):=if k=0 then 1 else k*sum(((sum(binomial(m+k,i)*binomial(2*m+k-i-1,m+k-1),i,0,m))*binomial(n-m,k))/(m+k),m,0,n-k); /* _Vladimir Kruchinin_, Apr 20 2015 */

%o (PARI) T(n, k)= if (k==0, 1, k*sum(m=0,n-k,sum(i=0,m, binomial(m+k, i)*binomial(2*m+k-i-1, m+k-1)*binomial(n-m, k))/(m+k)));

%o tabl(nn) = {for (n=0, nn, for (k=0, n, print1(T(n, k), ", ");); print(););} \\ _Michel Marcus_, Apr 21 2015

%Y Cf. A006318.

%K nonn,tabl

%O 0,5

%A _Emeric Deutsch_, Dec 20 2004