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,1

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,

Links

Alois P. Heinz, Rows n = 1..150, flattened

Wikipedia, Schröder number

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)

Example

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

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
# Alternative:
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

Mathematica

b[x_, y_, t_] := b[x, y, t] = Expand[If[y < 0 || 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]]]];
T[n_, k_] := Coefficient[b[2*n, 0, 0], z, k];
Table[Table[T[n, k], {k, 0, n - 1}], { n, 1, 12}] // Flatten (* Jean-François Alcover, Oct 27 2025, after Alois P. Heinz *)

Prog

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

Crossrefs

Row sums give A006318.

T(2n,n) gives A385299.

Cf. A000108, A003516, A060693.

Sequence in context: A118919 A319120 A274404 * A263776 A145879 A231210

Adjacent sequences: A101279 A101280 A101281 * A101283 A101284 A101285

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 20 2004

Status

approved