|
%I #33 May 20 2022 10:21:13
%S 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,
%T 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,
%U 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
%N 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).
%H Alois P. Heinz, <a href="/A049604/b049604.txt">Antidiagonals n = 0..140, flattened</a>
%F From _Yu-Sheng Chang_, Jun 10 2020: (Start)
%F We separate the generating function, F(z,v), into four parts: Left, Middle, Right and Remaining.
%F 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.
%F Second, the left and right parts, L(z,v) and R(z,v), collect coefficients like:
%F 0
%F 1 1
%F 2 - 2
%F 3 1 1 3
%F 2 2 - 2 2
%F 3 3 - - 3 3
%F 4 4 2 - 2 4 4
%F 5 3 3 - - 3 3 5
%F 4 4 4 - - - 4 4 4
%F 5 5 5 3 - - 3 5 5 5
%F 6 6 4 4 - - - 4 4 6 6
%F 7 5 5 5 - - - - 5 5 5 7
%F 6 6 6 6 4 - - - 4 6 6 6 6
%F 7 7 7 5 5 - - - - 5 5 7 7 7
%F 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.
%F Third, the middle part, M(z,v) collects:
%F -
%F - -
%F - - -
%F - - - -
%F - - - - -
%F - - - - - -
%F - - - 2 - - -
%F - - - 3 3 - - -
%F - - - 4 4 4 - - -
%F - - - - 3 3 - - - -
%F - - - - 4 4 4 - - - -
%F - - - - 5 5 5 5 - - - -
%F - - - - - 4 4 4 - - - - -
%F - - - - - 5 5 5 5 - - - - -
%F - - - - - 6 6 6 6 6 - - - - -
%F 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).
%F Finally, F(z,v) = L(z,v) + M(z,v) + R(z,v) + X(z,v), so we have:
%F 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).
%F (End)
%e Array T begins:
%e 0, 3, 2, 3, 2, 3, 4, 5, 4, 5, 6, ...
%e 3, 4, 1, 2, 3, 4, 3, 4, 5, 6, 5, ...
%e 2, 1, 4, 3, 2, 3, 4, 5, 4, 5, 6, ...
%e 3, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, ...
%e 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, ...
%e 3, 4, 3, 4, 3, 4, 5, 4, 5, 6, 5, ...
%e 4, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, ...
%e 5, 4, 5, 4, 5, 4, 5, 6, 5, 6, 7, ...
%e 4, 5, 4, 5, 4, 5, 6, 5, 6, 7, 6, ...
%e 5, 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, ...
%e 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, ...
%p A := proc(n,k) option remember;
%p local x;
%p if k = 0 then
%p if n = 1 then
%p 3
%p else
%p 2*floor(n/4)+ `mod`(n, 4)
%p end if;
%p elif k = 1 then
%p x := n - k + 1;
%p if x = 1 then
%p 3
%p elif x = 2 then
%p 4
%p else
%p 2*floor((n+1)*(1/4))-1 + `mod`(n+1, 4)
%p end if ;
%p elif n < 2*k then
%p A(n, n - k)
%p else ## n >= 2*k and n >= k >= 2
%p 1 + min(A(n-3,k-2), A(n-3,k-1))
%p end if;
%p end proc: # _Yu-Sheng Chang_, Jun 10 2020
%t A[n_ /; n >= 0, k_ /; k >= 0] := A[n, k] = Module[{x}, Which[
%t k == 0, If[n == 1, 3, 2*Floor[n/4] + Mod[n, 4]],
%t k == 1, x = n - k + 1;
%t Which[x == 1, 3, x == 2, 4,
%t True, 2*Floor[(n + 1)*(1/4)] - 1 + Mod[n + 1, 4]], n < 2*k, A[n, n - k],
%t True, 1 + Min[A[n - 3, k - 2], A[n - 3, k - 1]]]];
%t A[_, _] = 0;
%t T[n_, k_] := A[n + k, k];
%t Table[T[n - k, k], {n, 0, 13}, {k, 0, n}] // Flatten
%t (* _Jean-François Alcover_, May 20 2022, after _Yu-Sheng Chang_ *)
%K nonn,tabl,look
%O 0,2
%A _Clark Kimberling_
|
