|
| |
|
|
A049604
|
|
Array T read by diagonals: T(i,j)=least number of knight's moves on unbounded chessboard from corner (0,0) to square (i,j).
|
|
9
|
|
|
|
0, 3, 3, 2, 4, 2, 3, 1, 1, 3, 2, 2, 4, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 2, 2, 4, 4, 5, 3, 3, 3, 3, 3, 3, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 3, 3, 3, 3, 5, 5, 5, 6, 6, 4, 4, 4, 4, 4, 4, 4, 6, 6, 7, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 7, 6, 6, 6, 6, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 7, 7, 5, 5, 5, 5, 5, 5, 5, 5, 7, 7, 7
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
LINKS
|
|
|
|
FORMULA
|
We separate the generating function, F(z,v), into four parts: Left, Middle, Right and Remaining.
First, changing some entries and these lost terms are the Remaining part, X(z,v): T(1,0)=T(0,1)=1, T(2,2)=0, T(3,4)=T(4,3)=0, so X(z,v) = 2*(1+v)*z+4*v*z^2+4*v^2*z^4+3*(1+v)*v^2*z^5.
Second, the left and right parts, L(z,v) and R(z,v), collect coefficients like:
0
1 1
2 - 2
3 1 1 3
2 2 - 2 2
3 3 - - 3 3
4 4 2 - 2 4 4
5 3 3 - - 3 3 5
4 4 4 - - - 4 4 4
5 5 5 3 - - 3 5 5 5
6 6 4 4 - - - 4 4 6 6
7 5 5 5 - - - - 5 5 5 7
6 6 6 6 4 - - - 4 6 6 6 6
7 7 7 5 5 - - - - 5 5 7 7 7
Then R(z,v) = Sum_{j>=0} ((v^2*z^3)^j*(Sum_{i>=0} (((2*i+j)*(v*z)^0+(2*i+j+1)*(v*z)^1+(2*i+j+2)*(v*z)^2+(2*i+j+3)*(v*z)^3)*(v*z)^(4*i)))) = v*z*(1+z*v+z^2*v+z^2*v^2-z^3*v^2-z^3*v^3-z^4*v^3-z^5*v^4)/((1+z*v)*(1+z^2*v^2)*(1-z*v)^2*(1-z^3*v^2)^2) and L(z,v) = R(v*z,1/v) since it's symmetric.
Third, the middle part, M(z,v) collects:
-
- -
- - -
- - - -
- - - - -
- - - - - -
- - - 2 - - -
- - - 3 3 - - -
- - - 4 4 4 - - -
- - - - 3 3 - - - -
- - - - 4 4 4 - - - -
- - - - 5 5 5 5 - - - -
- - - - - 4 4 4 - - - - -
- - - - - 5 5 5 5 - - - - -
- - - - - 6 6 6 6 6 - - - - -
Then M(z,v) = Sum_{i=>0} (v^3*z^6*(v*z^3)^i*((i+2)*(1-v^(i+1))/(1-v)+(i+3)*(1-v^(i+2))*z/(1-v)+(i+4)*(1-v^(i+3))*z^2/(1-v))) = v^3*z^6*(2+3*z+3*z*v+4*z^2+4*z^2*v+4*z^2*v^2-z^3*v-z^3*v^2-2*z^4*v-8*z^4*v^2-3*z^5*v-2*z^4*v^3-11*z^5*v^2-11*z^5*v^3-3*z^5*v^4+4*z^7*v^3+4*z^7*v^4+6*z^8*v^3+10*z^8*v^4+6*z^8*v^5-2*z^10*v^5-3*z^11*v^5-3*z^11*v^6)/((1-z^3*v^2)^2*(1-z^3*v)^2).
Finally, F(z,v) = L(z,v) + M(z,v) + R(z,v) + X(z,v), so we have:
O.g.f.: F(z,v) = (2*v^10*z^20-2*v^9*(v+1)*z^19+4*v^9*z^18-2*v^8*(v+1)*z^17-2*v^6*(v^4-v^2+1)*z^16+2*v^5*(v+1)*(v^4-v^2+1)*z^15-2*v^5*(2*v^4-v^2+2)*z^14+v^4*(v+1)*(2*v^4+2*v^3-v^2+2*v+2)*z^13-v^4*(2*v^4+v^3-4*v^2+v+2)*z^12+v^3*(v+1)*(2*v^4-v^3-3*v^2-v+2)*z^11-v^3*(3*v^2-5*v+3)*(v+1)^2*z^10-v*(v+1)*(2*v^6+3*v^3+2)*z^9+v*(2*v^6-v^5+2*v^4+4*v^3+2*v^2-v+2)*z^8+v*(v+1)*(v^4+2*v^3-4*v^2+2*v+1)*z^7+(2*v^6+v^5+4*v^3+v+2)*z^6-(v+1)*(2*v^4-2*v^3+v^2-2*v+2)*z^5-(v^4+3*v^3+3*v+1)*z^4+(v+1)*(v^2-3*v+1)*z^3-(v+1)^2*z^2+3*(v+1)*z)/(v*z+1)/(z+1)/(v^2*z^2+1)/(z^2+1)/(v*z-1)^2/(z-1)^2/(v^2*z^3-1)/(v*z^3-1).
(End)
|
|
|
EXAMPLE
|
Array T begins:
0, 3, 2, 3, 2, 3, 4, 5, 4, 5, 6, ...
3, 4, 1, 2, 3, 4, 3, 4, 5, 6, 5, ...
2, 1, 4, 3, 2, 3, 4, 5, 4, 5, 6, ...
3, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, ...
2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, ...
3, 4, 3, 4, 3, 4, 5, 4, 5, 6, 5, ...
4, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, ...
5, 4, 5, 4, 5, 4, 5, 6, 5, 6, 7, ...
4, 5, 4, 5, 4, 5, 6, 5, 6, 7, 6, ...
5, 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, ...
6, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, ...
|
|
|
MAPLE
|
A := proc(n, k) option remember;
local x;
if k = 0 then
if n = 1 then
3
else
2*floor(n/4)+ `mod`(n, 4)
end if;
elif k = 1 then
x := n - k + 1;
if x = 1 then
3
elif x = 2 then
4
else
2*floor((n+1)*(1/4))-1 + `mod`(n+1, 4)
end if ;
elif n < 2*k then
A(n, n - k)
else ## n >= 2*k and n >= k >= 2
1 + min(A(n-3, k-2), A(n-3, k-1))
end if;
|
|
|
MATHEMATICA
|
A[n_ /; n >= 0, k_ /; k >= 0] := A[n, k] = Module[{x}, Which[
k == 0, If[n == 1, 3, 2*Floor[n/4] + Mod[n, 4]],
k == 1, x = n - k + 1;
Which[x == 1, 3, x == 2, 4,
True, 2*Floor[(n + 1)*(1/4)] - 1 + Mod[n + 1, 4]], n < 2*k, A[n, n - k],
True, 1 + Min[A[n - 3, k - 2], A[n - 3, k - 1]]]];
A[_, _] = 0;
T[n_, k_] := A[n + k, k];
Table[T[n - k, k], {n, 0, 13}, {k, 0, n}] // Flatten
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
