A339654 Number of lattice paths from (0,0) to (n,n) using steps (1,0), (0,1), (1,1), (-1,1) and whose points lie entirely in the integer square of lattice points {(i,j): 0 <= i,j <= n}.

1, 4, 33, 341, 3860, 45801, 558967, 6949276, 87529800, 1113178232, 14262575360, 183817376373, 2380397391739, 30947782216312, 403696062660177, 5280951542877725, 69252255466431356, 910088352234643128, 11982557663480438404, 158029913929209576448

Offset

0,2

Links

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

M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013, Volume 30, Issue 6, pp 1427-1452.

Formula

a(n) = A232968(n,n).

Recurrence: 2*(n+1)*(2*n + 1)*(6426*n^6 - 34821*n^5 + 75342*n^4 - 110997*n^3 + 137126*n^2 - 89704*n + 14688)*a(n) = 2*(205632*n^8 - 870084*n^7 + 1065120*n^6 - 1064055*n^5 + 3636646*n^4 - 6605153*n^3 + 5705054*n^2 - 2451496*n + 337824)*a(n-1) - 2*(436968*n^8 - 1609560*n^7 + 1220388*n^6 - 1075731*n^5 + 7315348*n^4 - 10572257*n^3 + 2273876*n^2 + 3716864*n - 1706472)*a(n-2) + 3*(n-2)*(109242*n^7 - 219249*n^6 - 131205*n^5 - 326601*n^4 + 1315615*n^3 - 247542*n^2 - 821068*n + 335976)*a(n-3) - 6*(n-3)*(n-2)*(6426*n^6 + 3735*n^5 - 2373*n^4 - 29319*n^3 + 4367*n^2 + 17376*n - 1940)*a(n-4). - Vaclav Kotesovec, Dec 16 2020

Maple

b:= proc(x, y, m) option remember; `if`(x=0 and y=0, 1,
      `if`(x>0, b(x-1, y, m), 0)+`if`(y>0, b(x, y-1, m), 0)+
      `if`(x>0 and y>0, b(x-1, y-1, m), 0)+
      `if`(x<m and y>0, b(x+1, y-1, m), 0))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..23);

Mathematica

Table[SeriesCoefficient[2^(n + 2) * (1 + x)^n * Sqrt[1 - 6*x - 3*x^2]/((1 - x + Sqrt[1 - 6*x - 3*x^2])^(n + 2) - (1 - x - Sqrt[1 - 6*x - 3*x^2])^(n + 2)), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Dec 16 2020 *)

Crossrefs

Main diagonal of A232968.

Sequence in context: A028576 A093185 A198006 * A347749 A362604 A075132

Adjacent sequences: A339651 A339652 A339653 * A339655 A339656 A339657

Keyword

nonn

Author

Alois P. Heinz, Dec 11 2020

Status

approved