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

1, 1, 11, 155, 2554, 46377, 899107, 18269407, 384577010, 8321452706, 184074021999, 4145999605431, 94799675260406, 2195442934642375, 51402741095491155, 1214975868437406375, 28956949406425290114, 695214262740084758154, 16800125921481031616230, 408354422827279445763942

Offset

0,3

Comments

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.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..703

Wikipedia, Schröder number

Formula

a(n) = A101282(2n,n).

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.

a(n) ~ 3^(3*n + 5/2) / (50*Pi*n^2). - Vaclav Kotesovec, Jun 27 2025

Example

a(0) = 1: the empty path.
a(1) = 1: UDUD.
a(2) = 11: HUDUDUD, UUDDUDUD, UHDUDUD, UDUUDDUD, UUDUDDUD, UDUHDUD, UDUDUUDD, UDUUDUDD, UUDUDUDD, UDUDUHD, UDUDUDH.

Maple

b:= proc(x, y, t, c) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, `if`(c=0, 1, 0), b(x-1, y-1, 1, c+1)+
        b(x-1, y+1, 0, c+1-4*t)+b(x-2, y, 0, c+2)))
    end:
a:= n-> b(4*n, 0$3):
seq(a(n), n=0..19);

Crossrefs

Cf. A006318, A007004 (the same for peaks), A101282.

Sequence in context: A223779 A191534 A243947 * A156933 A242008 A158512

Adjacent sequences: A385296 A385297 A385298 * A385300 A385301 A385302

Keyword

nonn

Author

Alois P. Heinz, Jun 24 2025

Status

approved