A225041 Number of lattice paths from (0,0) to (n,0) that do not go below the x-axis or above the diagonal x=y and consist of steps U=(1,1), D=(1,-1), H=(1,0) and S=(0,1).

1, 1, 3, 9, 35, 145, 659, 3137, 15619, 80177, 422595, 2273633, 12447667, 69138193, 388784259, 2209440945, 12671782579, 73260414481, 426545078627, 2499059841249, 14723542302627, 87181150961361, 518554078448339, 3097007445391441, 18565515801339827

Offset

0,3

Links

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

Formula

a(n) ~ c * (3+2*sqrt(3))^n / n^(3/2), where c = 0.05641378816540215191327201376... . - Vaclav Kotesovec, Sep 07 2014

Example

a(0) = 1: the empty path.
a(1) = 1: H.
a(2) = 3: HH, UD, HSD.
a(3) = 9: HHH, UDH, HSDH, UHD, HSHD, HUD, HHSD, UDSD, HSDSD.

Maple

b:= proc(x, y) option remember; `if`(y>x, 0, `if`(x=0, 1,
       b(x-1, y)+`if`(y>0, b(x-1, y-1)+b(x, y-1), 0)+b(x-1, y+1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);

Mathematica

b[x_, y_] := b[x, y] = If[y>x, 0, If[x==0, 1, b[x-1, y]+If[y>0, b[x-1, y-1] + b[x, y-1], 0] + b[x-1, y+1]]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

Crossrefs

Cf. A001006 (without S-steps), A114296 (without U-steps), A198324 (without H-steps), A225042 (paths to (n,n)), A286760.

Sequence in context: A046697 A151045 A369389 * A335642 A327885 A074507

Adjacent sequences: A225038 A225039 A225040 * A225042 A225043 A225044

Keyword

nonn

Author

Alois P. Heinz, Apr 25 2013

Status

approved