A339565 Number of lattice paths from (0,0) to (n,n) using steps (0,1), (1,0), (1,1), (1,2), (2,1).

1, 3, 17, 101, 627, 3999, 25955, 170571, 1131433, 7559301, 50795985, 342935689, 2324278669, 15804931797, 107775401349, 736723618773, 5046774983235, 34636814325087, 238114193665451, 1639378334244867, 11301978856210543, 78010917772099207, 539055832175992119

Offset: 0

Author

Kent Mei, Dec 08 2020

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1179 (first 101 terms from Kent Mei)

Crossrefs

Cf. A000984, A001850, A137635, A339390, A382436.

Programs

Maple

a:= proc(n) local t; 1/(1-x-y-x*y-(x*y^2)-(x^2*y));
      for t in [x, y] do coeftayl(%, t=0, n) od
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 09 2020
# second Maple program:
b:= proc(l) option remember; `if`(l[2]=0, 1,
      add((f-> `if`(f[1]<0, 0, b(f)))(sort(l-h)), h=
      [[1, 0], [0, 1], [1$2], [1, 2], [2, 1]]))
    end:
a:= n-> b([n$2]):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 09 2020
# third Maple program:
a:= proc(n) option remember; `if`(n<3, [1, 3, 17][n+1],
      ((6*n-3)*a(n-1)+(7*n-7)*a(n-2)+(4*n-6)*a(n-3))/n)
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 09 2020

Mathematica

b[l_] := b[l] = If[l[[2]] == 0, 1,
     Sum[Function[f, If[f[[1]] < 0, 0, b[f]]][Sort[l - h]], {h,
     {{1, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 1}}}]];
a[n_] := b[{n, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, May 30 2022, after Alois P. Heinz *)

Formula

a(n) = [(x*y)^n] 1/(1-x-y-x*y-x*y^2-x^2*y). - Alois P. Heinz, Dec 09 2020

a(n) = A382436(2n,n). - Alois P. Heinz, Mar 25 2025

a(n) ~ sqrt((3776 + (26570110976 - 74946048*sqrt(177))^(1/3) + 8*(59*(879572 + 2481*sqrt(177)))^(1/3))/11328) * (2 + (459 - 12*sqrt(177))^(1/3)/3 + (153 + 4*sqrt(177))^(1/3)/3^(2/3))^n / sqrt(Pi*n). - Vaclav Kotesovec, Mar 26 2025