|
| |
|
|
A186851
|
|
Array read by antidiagonals: T(n,k) = number of n-step knight's tours on a (k+2)X(k+2) board summed over all starting positions.
|
|
8
|
|
|
|
9, 16, 16, 25, 48, 16, 36, 96, 104, 16, 49, 160, 328, 208, 16, 64, 240, 664, 976, 400, 16, 81, 336, 1112, 2576, 2800, 800, 16, 100, 448, 1672, 5056, 9328, 8352, 1280, 16, 121, 576, 2344, 8320, 21480, 34448, 21664, 2208, 0, 144, 720, 3128, 12368, 39616, 91328
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Here an n-step knight's tour is a directed path with n vertices (or a self-avoiding walk with n-1 steps). - Andrew Howroyd, Jan 02 2023
|
|
|
LINKS
|
|
|
|
FORMULA
|
Empirical, for all rows: a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>3,3,4,6,8,10 respectively for row in 1..6.
The above empirical formula is correct. Equivalently T(m,n) for given m and n >= 2*m-4 is given by a quadratic polynomial in n. This is because a w X h rectangle can be placed on a k X k grid at integer coordinates in (k-w+1)*(k-h+1) ways when w and h are at most k and every knights path with m vertices spans such a rectangle with width and height at most 2*m - 1.
Sum_{i=2..(k+2)^2} T(i,k)/2 = A289204(k+2).
T(n,k) = 0 for n > (k-2)^2.
(End)
|
|
|
EXAMPLE
|
Table starts:
9 16 25 36 49 64 81 100 121 144 ...
16 48 96 160 240 336 448 576 720 880 ...
16 104 328 664 1112 1672 2344 3128 4024 5032 ...
16 208 976 2576 5056 8320 12368 17200 22816 29216 ...
16 400 2800 9328 21480 39616 63440 92656 127264 167264 ...
16 800 8352 34448 91328 186544 322528 498320 712080 ...
16 1280 21664 118480 372384 847520 1584576 2596480 ...
16 2208 57392 405040 1508784 3846192 7777808 ...
0 3184 135184 1290112 5807488 ...
0 4640 317296 4089632 ...
...
Some n=3 solutions for 5X5:
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0
0 0 0 3 0 0 3 0 0 0 2 0 0 0 0 3 0 0 0 1
0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0
|
|
|
PROG
|
(PARI) \\ G(n) gives polynomial valid for k >= 2*n-4.
Knights={[1, 2; 1, -2; -1, 2; -1, -2; 2, 1; 2, -1; -2, 1; -2, -1]}
G(n, f=i->'n-(i-2)) = {
local(x=vector(n), y=vector(n));
my(recurse(k)=
forstep(i=2-k%2, k-1, 2, if(x[i]==x[k] && y[i]==y[k], return(0)));
if (k==n, f(vecmax(x)-vecmin(x))*f(vecmax(y)-vecmin(y)), sum(i=1, 8, x[k+1] = x[k]+Knights[i, 1]; y[k+1]=y[k]+Knights[i, 2]; self()(k+1)) );
);
if(n==1, recurse(1), x[1]=1; y[1]=2; 8*recurse(2))
}
row(m, n)={my(p=if(n>=2*m-4, G(m, i->'x-(i-2)))); vector(n, k, if(k>=2*m-4, subst(p, 'x, k), G(m, i->max(0, k+2-i))))} \\ Andrew Howroyd, Jan 02 2023
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
