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