cp's OEIS Frontend

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

%I A101282 #33 Jun 25 2025 21:12:11
%S A101282 2,5,1,14,7,1,42,36,11,1,132,165,80,16,1,429,715,484,155,22,1,1430,
%T A101282 3003,2639,1183,273,29,1,4862,12376,13468,7840,2554,448,37,1,16796,
%U A101282 50388,65688,47328,20124,5031,696,46,1,58786,203490,310080,267444,141219,46377,9230,1035,56,1
%N A101282 Triangle read by rows: T(n,k) is the number of Schroeder paths of length 2n and having k valleys.
%C A101282 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,
%H A101282 Alois P. Heinz, <a href="/A101282/b101282.txt">Rows n = 1..150, flattened</a>
%H A101282 Wikipedia, <a href="https://en.wikipedia.org/wiki/Schr%C3%B6der_number">Schröder number</a>
%F A101282 G.f.: G=G(t, z) satisfies z(t+z-tz)G^2-(1-2z+tz)G+1=0.
%F A101282 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
%F A101282 From _Mikhail Kurkov_, Jun 17 2025: (Start)
%F A101282 Conjecture: The n-th row polynomial is R(n+1,0) where
%F A101282   R(n,n) = 1,
%F A101282   R(n,0) = Sum_{j=0..n-1} R(n-1,j) for n > 0,
%F A101282   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)
%e A101282 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.
%e A101282 Triangle begins:
%e A101282     2;
%e A101282     5,   1;
%e A101282    14,   7,  1;
%e A101282    42,  36, 11,  1;
%e A101282   132, 165, 80, 16, 1;
%e A101282   ...
%p A101282 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
%p A101282 # second Maple program:
%p A101282 b:= proc(x, y, t) option remember; expand(`if`(y<0 or y>x, 0,
%p A101282      `if`(x=0, 1, b(x-1, y-1, 1)+b(x-1, y+1, 0)*z^t+b(x-2, y, 0))))
%p A101282     end:
%p A101282 T:= (n, k)-> coeff(b(2*n, 0$2), z, k):
%p A101282 seq(seq(T(n,k), k=0..n-1), n=1..12);  # _Alois P. Heinz_, Jun 17 2025
%o A101282 (Maxima)
%o A101282 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 */
%Y A101282 Row sums give A006318.
%Y A101282 T(2n,n) gives A385299.
%Y A101282 Cf. A000108, A003516, A060693.
%K A101282 nonn,tabl
%O A101282 1,1
%A A101282 _Emeric Deutsch_, Dec 20 2004