cp's OEIS Frontend

A385299 Number of Schröder paths of semilength 2n and having n valleys.

%I A385299 #25 Jul 02 2025 22:46:56
%S A385299 1,1,11,155,2554,46377,899107,18269407,384577010,8321452706,
%T A385299 184074021999,4145999605431,94799675260406,2195442934642375,
%U A385299 51402741095491155,1214975868437406375,28956949406425290114,695214262740084758154,16800125921481031616230,408354422827279445763942
%N A385299 Number of Schröder paths of semilength 2n and having n valleys.
%C A385299 A Schröder path of semilength n 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.
%H A385299 Alois P. Heinz, <a href="/A385299/b385299.txt">Table of n, a(n) for n = 0..703</a>
%H A385299 Wikipedia, <a href="https://en.wikipedia.org/wiki/Schr%C3%B6der_number">Schröder number</a>
%F A385299 a(n) = A101282(2n,n).
%F A385299 a(n) = Sum_{k=0..n-1} (k+1)/(2*n-k)*C(2*n-k,n)*C(3*n-k,2*n+1) for n>=1, a(0) = 1.
%F A385299 a(n) ~ 3^(3*n + 5/2) / (50*Pi*n^2). - _Vaclav Kotesovec_, Jun 27 2025
%e A385299 a(0) = 1: the empty path.
%e A385299 a(1) = 1: UDUD.
%e A385299 a(2) = 11: HUDUDUD, UUDDUDUD, UHDUDUD, UDUUDDUD, UUDUDDUD, UDUHDUD, UDUDUUDD, UDUUDUDD, UUDUDUDD, UDUDUHD, UDUDUDH.
%p A385299 b:= proc(x, y, t, c) option remember; `if`(y<0 or y>x, 0,
%p A385299      `if`(x=0, `if`(c=0, 1, 0), b(x-1, y-1, 1, c+1)+
%p A385299         b(x-1, y+1, 0, c+1-4*t)+b(x-2, y, 0, c+2)))
%p A385299     end:
%p A385299 a:= n-> b(4*n, 0$3):
%p A385299 seq(a(n), n=0..19);
%Y A385299 Cf. A006318, A007004 (the same for peaks), A101282.
%K A385299 nonn
%O A385299 0,3
%A A385299 _Alois P. Heinz_, Jun 24 2025