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

 

Logo
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
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
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.

License Agreements, Terms of Use, Privacy Policy. .

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