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.

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, 103, 16, 1, 1, 3001, 2973, 1753, 659, 151, 19, 1, 1, 13880, 13844, 8716, 3798, 1116, 208, 22, 1, 1, 66345, 66300, 43384, 20798, 7226, 1744, 274, 25, 1, 1, 324908, 324853, 217804

Offset: 0

Author

Emeric Deutsch, Dec 20 2004

Keywords

• nonn
• tabl

Comments

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

Examples

			T(2,1)=4 because we have UHD, UUDD, HUD and UDH.
Triangle begins:
  1;
  1,  1;
  1,  4,  1;
  1, 13,  7,  1;
  1, 44, 34, 10, 1;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Cf. A006318.

Programs

Maple

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

Maxima

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 */

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)));
tabl(nn) = {for (n=0, nn, for (k=0, n, print1(T(n, k), ", ");); print(););} \\ Michel Marcus, Apr 21 2015

Formula

G.f.: 2/(2-2*z-t+t*z+t*sqrt(1-6*z+z^2)).

1/(1-x-xy/(1-x-x/(1-x-x/(1-x-x/(1-x-x/(1-.... (continued fraction). - Paul Barry, Feb 01 2009

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