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

Author

Alois P. Heinz, Apr 25 2013

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

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

Programs

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

Formula

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