A198324 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) and S=(0,1).

1, 0, 1, 1, 4, 10, 35, 116, 427, 1584, 6146, 24216, 97754, 400080, 1662645, 6986127, 29669872, 127101015, 548839687, 2386211664, 10439207266, 45920497075, 203004397362, 901459381683, 4019351034816, 17987665701788, 80773320086286, 363842478143834

Offset: 0

Author

Alois P. Heinz, Apr 18 2013

Keywords

• nonn

Examples

			a(4) = 4: UDSDSD, UDUD, UDSSDD, UUDD.
a(5) = 10: UDSDSDSD, UDUDSD, UDSSDDSD, UUDDSD, UDSDUD, UDSDSSDD, UDUSDD, UDSSDSDD, UUDSDD, UDSUDD.
		

Links

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

Crossrefs

Cf. A000108 (without S-steps), A224769 (paths to (n,n)), A225041 (with additional H-steps), A286427.

Programs

Maple

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

Mathematica

b[x_, y_] := b[x, y] = If[y>x, 0, If[x == 0, 1, If[y>0, b[x, y-1] + b[x-1, y-1], 0] + b[x-1, y+1]]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)

Formula

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