The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A367558 Number of knight paths from opposite corners of an n X n matrix, using only turns that lower Manhattan distance. 0
 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 (list; graph; refs; listen; history; text; internal format)
 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 16 11:34 EDT 2024. Contains 374347 sequences. (Running on oeis4.)