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

2, 5, 1, 14, 7, 1, 42, 36, 11, 1, 132, 165, 80, 16, 1, 429, 715, 484, 155, 22, 1, 1430, 3003, 2639, 1183, 273, 29, 1, 4862, 12376, 13468, 7840, 2554, 448, 37, 1, 16796, 50388, 65688, 47328, 20124, 5031, 696, 46, 1, 58786, 203490, 310080, 267444, 141219, 46377, 9230, 1035, 56, 1

Offset: 1

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

Examples

			T(3,1) = 7 because we have HU(DU)D, U(DU)DH, U(DU)HD, UH(DU)D, U(DU)UDD, UUD(DU)D and UU(DU)DD, the valleys being shown between parentheses.
Triangle begins:
    2;
    5,   1;
   14,   7,  1;
   42,  36, 11,  1;
  132, 165, 80, 16, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..150, flattened
• Wikipedia, Schröder number

Crossrefs

Row sums give A006318.

T(2n,n) gives A385299.

Cf. A000108, A003516, A060693.

Programs

Maple

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
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
     `if`(x=0, 1, b(x-1, y-1, 1)+b(x-1, y+1, 0)*z^t+b(x-2, y, 0))))
    end:
T:= (n, k)-> coeff(b(2*n, 0$2), z, k):
seq(seq(T(n,k), k=0..n-1), n=1..12);  # Alois P. Heinz, Jun 17 2025

Maxima

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

Formula

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

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

From Mikhail Kurkov, Jun 17 2025: (Start)

Conjecture: The n-th row polynomial is R(n+1,0) where

R(n,n) = 1,

R(n,0) = Sum_{j=0..n-1} R(n-1,j) for n > 0,

R(n,k) = R(n-1,k-1) + (x+1) * (R(n,0) - Sum_{j=0..k-1} R(n-1,j)) for 0 < k < n. (End)