cp's OEIS Frontend

A101275 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.

%I A101275 #18 May 02 2025 08:01:32
%S A101275 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 A101275 103,16,1,1,3001,2973,1753,659,151,19,1,1,13880,13844,8716,3798,1116,
%U A101275 208,22,1,1,66345,66300,43384,20798,7226,1744,274,25,1,1,324908,324853,217804
%N A101275 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 A101275 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 A101275 Alois P. Heinz, <a href="/A101275/b101275.txt">Rows n = 0..140, flattened</a>
%F A101275 G.f.: 2/(2-2*z-t+t*z+t*sqrt(1-6*z+z^2)).
%F A101275 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 A101275 T(n,k) = k*Sum_{m=0..n-k} (C(n-m,k)/(m+k))*Sum_{i=0..m} C(m+k,i)*C(2*m+k-i-1,m+k-1), T(n,0) = 1. - _Vladimir Kruchinin_, Apr 20 2015
%e A101275 T(2,1)=4 because we have UHD, UUDD, HUD and UDH.
%e A101275 Triangle begins:
%e A101275   1;
%e A101275   1,  1;
%e A101275   1,  4,  1;
%e A101275   1, 13,  7,  1;
%e A101275   1, 44, 34, 10, 1;
%p A101275 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 A101275 (Maxima)
%o A101275 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 A101275 (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 A101275 tabl(nn) = {for (n=0, nn, for (k=0, n, print1(T(n, k), ", ");); print(););} \\ _Michel Marcus_, Apr 21 2015
%Y A101275 Cf. A006318.
%K A101275 nonn,tabl
%O A101275 0,5
%A A101275 _Emeric Deutsch_, Dec 20 2004