|
|
A225042
|
|
Number of lattice paths from (0,0) to (n,n) 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).
|
|
7
|
|
|
1, 2, 8, 48, 360, 3088, 28928, 288208, 3003952, 32402384, 359019952, 4064452272, 46829600704, 547498996736, 6480275672192, 77511461858592, 935562094075392, 11381614588917296, 139425068741674448, 1718444636265140992, 21295889048851102176, 265200380258393530896
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ c * d^n / n^(3/2), where d = 1/6*(19009+153*sqrt(17))^(1/3) + 356/(3*(19009+153*sqrt(17))^(1/3)) + 14/3 = 13.56165398271839628518..., c = 0.03237684690282108810066870410351693504744294274892020985727414558915214336... - Vaclav Kotesovec, Sep 07 2014, updated Sep 13 2021
|
|
EXAMPLE
|
a(0) = 1: the empty path.
a(1) = 2: U, HS.
a(2) = 8: UU, HSU, UHS, HSHS, HUS, HHSS, UDSS, HSDSS.
|
|
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, n):
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, n];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|