cp's OEIS Frontend

A120399 Consider n x n chessboard. This sequence gives number of chess knight paths from left bottom corner of the board to the right top corner with minimal possible path length (shortest paths).

%I A120399 #6 Jan 28 2015 11:21:06
%S A120399 1,0,2,2,8,4,6,108,40,20,858,252,70,5596,1344,252,32814,6600,924,
%T A120399 179696,30888,3432,937794,140140,12870,4721964,622336,48620,23127208,
%U A120399 2720952,184756,110809672,11757200,705432,521527428,50338904,2704156,2418585240,213955200
%N A120399 Consider n x n chessboard. This sequence gives number of chess knight paths from left bottom corner of the board to the right top corner with minimal possible path length (shortest paths).
%C A120399 Generating function for this sequence obeys the following second order algebraic equation: x^7*(4*x^3 - 1)^5*g(x)^2 - 2*(4*x^3 - 1)^5*(2*x^10 - 2*x^9 - 2*x^7 - 3*x^6 + 4*x^4 + 36*x^3 - 19)*g(x) + (4096*x^28 - 8192*x^27 + 4096*x^26 - 13312*x^25 + 6144*x^24 + 32768*x^23 + 38400*x^22 + 189696*x^21 + 48128*x^20 - 10112*x^19 - 300288*x^18 - 76800*x^17 - 46320*x^16 + 189888*x^15 + 27824*x^14 + 52492*x^13 - 65080*x^12 + 1876*x^11 - 24840*x^10 + 13181*x^9 - 2404*x^8 + 6074*x^7 - 1512*x^6 + 296*x^5 - 756*x^4 + 76*x^3 + 38*x)=0.
%F A120399 Let K(n) equal shortest path length. Then for n>3 K(n)=2[(n+1)/3], where [x]=floor(x). a(n)=2*(K-2)*binomial(K-1,K/2-2), if n mod 3 = 0 a(n)=binomial(K,K/2), if n mod 3 = 1 a(n)=(K-2)*(K-3)*binomial(K-2,K/2-1)+2*((K-2)*binomial(K-1,K/2-2)- 2*binomial(K-2,K/2-3))+2*(binomial(K-2,2)*binomial(K-2,K/2-4)- 2*binomial(K-3,K/2-5)), if n mod 3 = 2
%F A120399 In the above expressions binomial(x,y) = x!/(y!(x - y)!). g(x) = ( - (2*x^9 + 3*x^6 - 36*x^3 + 19) + 2*(7*x^9 - 14*x^6 + 7*x^3 - 1)/(1 - 4*x^3)^(1/2) + 2*x^3*(10*x^9 - 36*x^6 + 21*x^3 - 3)/(1 - 4*x^3)^(3/2) + (16*x^15 + 860*x^12 - 1710*x^9 + 1039*x^6 - 250*x^3 + 21)/(1 - 4*x^3)^(5/2))/x^7 + x/(1 - 4*x^3)^(1/2) - 2 + 4/x^3 + 2*x^3 - 2*(2*x^3 - 1)*(9*x^3 - 2)/x^3/(1 - 4*x^3)^(3/2);
%e A120399 a(2)=0 because final path point is out of reach,
%e A120399 for n=3 K(3)=4, a(3)=2 (a1-b3-c1-a2-c3) or (a1-c2-a3-b1-c3)
%e A120399 a(4)=2 (a1-b3-d4) or (a1-c2-d4)
%K A120399 nonn
%O A120399 1,3
%A A120399 _Sergey Perepechko_, Jul 02 2006
%E A120399 a(18)-a(39) from _Alois P. Heinz_, Jan 28 2015