A367558 - OEIS

%I #31 Dec 17 2023 10:19:40

%S 0,1,0,0,2,4,14,56,244,1140,5482,26886,134528,681944,3493524,18057208,

%T 94018056,492534414,2593760854,13720433802,72859816050,388218182456,

%U 2074683905712,11116464683746,59702675780296,321311045089704,1732487750419756,9357244742176372,50616284630194342,274180772642526672,1487084387418749912

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

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

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

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

%C For n=0 the answer is ambigious

%C 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

%F a(0) = 0

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

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

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

%F 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)

%e For n=4 there are 2 paths from (0,0) to (3,3):

%e   {(1,2), (3,3)}, {(2,1), (3,3)}.

%e For n=5 there are 4 paths from (0,0) to (4,4):

%e   {(1,2),(0,4),(2,3),(4,4)}, {(1,2),(3,1),(2,3),(4,4)},

%e   {(2,1),(4,0),(3,2),(4,4)}, {(2,1),(1,3),(3,2),(4,4)}.

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

%o (Python)

%o cache = {}

%o def F(a,b,n):

%o     if (a,b,n) in cache: return cache[(a,b,n)]

%o     if a==0 and b==0: return 1

%o     if a > n or b > n: return 0

%o     if a < 0 or b < 0: return 0

%o     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)

%o     return cache[(a,b,n)]

%o for i in range (30):

%o     print(F(i,i,i), end=', ')

%K nonn,walk

%O 0,5

%A _Alexander Kuleshov_, Nov 28 2023