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
Keywords
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
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