A230662 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), U=(1,2), d=(1,-1), D=(1,-2) and H=(1,0).

1, 1, 2, 4, 10, 26, 74, 218, 668, 2096, 6726, 21946, 72666, 243504, 824528, 2816854, 9698520, 33620626, 117254340, 411135452, 1448544666, 5125796448, 18209367238, 64919822556, 232206203152, 833040115596, 2996741699470, 10807658186756, 39068847237770

Offset: 0

Author

Alois P. Heinz, Oct 28 2013

Keywords

• nonn

Examples

			a(0) = 1: the empty path.
a(1) = 1: u.
a(2) = 2: HU, uu.
a(3) = 4: HuU, uHU, HUu, uuu.
a(4) = 10: HHUU, udUU, HuuU, uHuU, HUHU, uuHU, HuUu, uHUu, HUuu, uuuu.
a(5) = 26:  HHuUU, uduUU, HuHUU, uHHUU, HUdUU, uudUU, HHUuU, udUuU, HuuuU, uHuuU, HUHuU, uuHuU, HuUHU, uHUHU, HUuHU, uuuHU, HHUUu, udUUu, HuuUu, uHuUu, HUHUu, uuHUu, HuUuu, uHUuu, HUuuu, uuuuu.
		

Links

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

Crossrefs

Cf. A225042.

Programs

Maple

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

Mathematica

b[x_, y_] := b[x, y] = If[y > x || y < 0, 0,
   If[x == 0, 1, Sum[b[x - 1, y + j], {j, -2, 2}]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 28 2022, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n / n^(3/2), where d = 47/54 + (1/54)*sqrt(2479 - (6525*15^(2/3))/(-8271 + 1496*sqrt(51))^(1/3) + 45*(15*(-8271 + 1496*sqrt(51)))^(1/3)) + (1/2)*sqrt(4958/729 + (725*5^(2/3))/(27*(3*(-8271 + 1496*sqrt(51)))^(1/3)) - (5*(5*(-8271 + 1496*sqrt(51)))^(1/3))/(27*3^(2/3)) + 318616/(729*sqrt(2479 - (6525*15^(2/3))/(-8271 + 1496*sqrt(51))^(1/3) + 45*(15*(-8271 + 1496*sqrt(51)))^(1/3)))) = 3.8344372490288055637652411266... and c = 0.2279529551507616709766813416011544206054574311958828512... - Vaclav Kotesovec, Oct 30 2013, updated Sep 11 2021