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

1, 1, 2, 4, 12, 34, 118, 396, 1508, 5670, 22773, 91337, 381157, 1597683, 6855957, 29599117, 129748149, 572349631, 2551033858, 11435935450, 51651644306, 234472103672, 1070461943299, 4908349870799, 22607570625188, 104515879798724, 484955119433493

Offset: 0

Author

Alois P. Heinz, Apr 14 2014

Keywords

• nonn

Examples

			a(0) = 1: the empty path.
a(1) = 1: H.
a(2) = 2: HH, ud.
a(3) = 4: HHH, udH, Hud, uHd.
a(4) = 12: HHHH, udHH, HudH, uHdH, HHud, udud, HuHd, uHHd, uudd, HHUD, udUD, uuuD.
a(5) = 34: HHHHH, udHHH, HudHH, uHdHH, HHudH, ududH, HuHdH, uHHdH, uuddH, HHUDH, udUDH, uuuDH, HHHud, udHud, Hudud, uHdud, HHuHd, uduHd, HuHHd, uHHHd, uudHd, Huudd, uHudd, uuHdd, HHHUD, udHUD, HudUD, uHdUD, HuuuD, uHuuD, uuHuD, HHUHD, udUHD, uuuHD.
		

Links

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

Crossrefs

Cf. A001006 (without steps U, D), A127902 (without steps U, d), A247748.

Row sums of A247749.

Programs

Maple

b:= proc(x, y) option remember; `if`(y<0 or x b(n, 0):
seq(a(n), n=0..30);

Mathematica

b[x_, y_] := b[x, y] = If[y<0 || xJean-François Alcover, Dec 20 2020, after Alois P. Heinz *)

Formula

a(n) ~ c * 5^n / n^(3/2), where c = 0.027245791342943908483296328462... . - Vaclav Kotesovec, Aug 28 2014