login
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

%I #26 Jun 28 2022 03:16:47

%S 1,1,2,4,10,26,74,218,668,2096,6726,21946,72666,243504,824528,2816854,

%T 9698520,33620626,117254340,411135452,1448544666,5125796448,

%U 18209367238,64919822556,232206203152,833040115596,2996741699470,10807658186756,39068847237770

%N 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).

%H Alois P. Heinz, <a href="/A230662/b230662.txt">Table of n, a(n) for n = 0..1000</a>

%F 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

%e a(0) = 1: the empty path.

%e a(1) = 1: u.

%e a(2) = 2: HU, uu.

%e a(3) = 4: HuU, uHU, HUu, uuu.

%e a(4) = 10: HHUU, udUU, HuuU, uHuU, HUHU, uuHU, HuUu, uHUu, HUuu, uuuu.

%e 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.

%p b:= proc(x, y) option remember; `if`(y>x or y<0, 0,

%p `if`(x=0, 1, add(b(x-1, y+j), j=-2..2)))

%p end:

%p a:= n-> b(n, n):

%p seq(a(n), n=0..30);

%t b[x_, y_] := b[x, y] = If[y > x || y < 0, 0,

%t If[x == 0, 1, Sum[b[x - 1, y + j], {j, -2, 2}]]];

%t a[n_] := b[n, n];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 28 2022, after _Alois P. Heinz_ *)

%Y Cf. A225042.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Oct 28 2013