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

Author

Alexander Kuleshov, Nov 28 2023

Keywords

• nonn
• walk

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

Examples

			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)}.
		

Programs

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 *)

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=', ')

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)