cp's OEIS Frontend

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

%I A367558 #31 Dec 17 2023 10:19:40
%S A367558 0,1,0,0,2,4,14,56,244,1140,5482,26886,134528,681944,3493524,18057208,
%T A367558 94018056,492534414,2593760854,13720433802,72859816050,388218182456,
%U A367558 2074683905712,11116464683746,59702675780296,321311045089704,1732487750419756,9357244742176372,50616284630194342,274180772642526672,1487084387418749912
%N A367558 Number of knight paths from opposite corners of an n X n matrix, using only turns that lower Manhattan distance.
%C A367558 Using only the turns that lowers Manhattan distance ensures that amount of paths is finite.
%C A367558 For n=2,3 there is not enough space to have any path to the opposite square.
%C A367558 For n=1 starting square is an end square, there is only an empty path.
%C A367558 For n=0 the answer is ambigious
%C A367558 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 A367558 a(0) = 0
%F A367558 a(n+1) = F(n,n,n)
%F A367558 F(a,b,n) = 1 if a=b=0 otherwise
%F A367558 F(a,b,n) = 0 if a<0 or b<0 or a>n or b>n otherwise
%F A367558 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 A367558 For n=4 there are 2 paths from (0,0) to (3,3):
%e A367558   {(1,2), (3,3)}, {(2,1), (3,3)}.
%e A367558 For n=5 there are 4 paths from (0,0) to (4,4):
%e A367558   {(1,2),(0,4),(2,3),(4,4)}, {(1,2),(3,1),(2,3),(4,4)},
%e A367558   {(2,1),(4,0),(3,2),(4,4)}, {(2,1),(1,3),(3,2),(4,4)}.
%t A367558 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 A367558 (Python)
%o A367558 cache = {}
%o A367558 def F(a,b,n):
%o A367558     if (a,b,n) in cache: return cache[(a,b,n)]
%o A367558     if a==0 and b==0: return 1
%o A367558     if a > n or b > n: return 0
%o A367558     if a < 0 or b < 0: return 0
%o A367558     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 A367558     return cache[(a,b,n)]
%o A367558 for i in range (30):
%o A367558     print(F(i,i,i), end=', ')
%K A367558 nonn,walk
%O A367558 0,5
%A A367558 _Alexander Kuleshov_, Nov 28 2023