A367558 Number of knight paths from opposite corners of an n X n matrix, using only turns that lower Manhattan distance.

0, 1, 0, 0, 2, 4, 14, 56, 244, 1140, 5482, 26886, 134528, 681944, 3493524, 18057208, 94018056, 492534414, 2593760854, 13720433802, 72859816050, 388218182456, 2074683905712, 11116464683746, 59702675780296, 321311045089704, 1732487750419756, 9357244742176372, 50616284630194342, 274180772642526672, 1487084387418749912

Offset

0,5

Comments

Using only the turns that lowers Manhattan distance ensures that amount of paths is finite.

For n=2,3 there is not enough space to have any path to the opposite square.

For n=1 starting square is an end square, there is only an empty path.

For n=0 the answer is ambigious

Conjecture: a(n+1)/a(n) tends to d = 5.566315770083119..., where d is the real root of the equation d^3 - 4*d^2 - 8*d - 4 = 0. - Vaclav Kotesovec, Nov 28 2023

Links

Table of n, a(n) for n=0..30.

Formula

a(0) = 0

a(n+1) = F(n,n,n)

F(a,b,n) = 1 if a=b=0 otherwise

F(a,b,n) = 0 if a<0 or b<0 or a>n or b>n otherwise

F(a,b,n) = F(a-1,b-2,n) + F(a-2,b-1,n) + F(a+1,b-2,n) + F(a-2,b+1,n)

Example

For n=4 there are 2 paths from (0,0) to (3,3):
  {(1,2), (3,3)}, {(2,1), (3,3)}.
For n=5 there are 4 paths from (0,0) to (4,4):
  {(1,2),(0,4),(2,3),(4,4)}, {(1,2),(3,1),(2,3),(4,4)},
  {(2,1),(4,0),(3,2),(4,4)}, {(2,1),(1,3),(3,2),(4,4)}.

Mathematica

F[a_, b_, n_] := F[a, b, n] = If[a == 0 && b == 0, 1, If[a < 0 || b < 0 || a > n || b > n, 0, F[a - 1, b - 2, n] + F[a - 2, b - 1, n] + F[a + 1, b - 2, n] + F[a - 2, b + 1, n]]]; Join[{0}, Table[F[n, n, n], {n, 0, 20}]] (* Vaclav Kotesovec, Nov 28 2023 *)

Prog

(Python)
cache = {}
def F(a, b, n):
    if (a, b, n) in cache: return cache[(a, b, n)]
    if a==0 and b==0: return 1
    if a > n or b > n: return 0
    if a < 0 or b < 0: return 0
    cache[(a, b, n)] = F(a-1, b-2, n) + F(a-2, b-1, n) + F(a+1, b-2, n) + F(a-2, b+1, n)
    return cache[(a, b, n)]
for i in range (30):
    print(F(i, i, i), end=', ')

Crossrefs

Sequence in context: A131180 A047990 A000939 * A109154 A030853 A306150

Adjacent sequences: A367555 A367556 A367557 * A367559 A367560 A367561

Keyword

nonn,walk

Author

Alexander Kuleshov, Nov 28 2023

Status

approved