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