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

1, 0, 2, 2, 8, 4, 6, 108, 40, 20, 858, 252, 70, 5596, 1344, 252, 32814, 6600, 924, 179696, 30888, 3432, 937794, 140140, 12870, 4721964, 622336, 48620, 23127208, 2720952, 184756, 110809672, 11757200, 705432, 521527428, 50338904, 2704156, 2418585240, 213955200

Offset: 1

Author

Sergey Perepechko, Jul 02 2006

Keywords

• nonn

Comments

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.

Examples

			a(2)=0 because final path point is out of reach,
for n=3 K(3)=4, a(3)=2 (a1-b3-c1-a2-c3) or (a1-c2-a3-b1-c3)
a(4)=2 (a1-b3-d4) or (a1-c2-d4)
		

Formula

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

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);

Extensions

a(18)-a(39) from Alois P. Heinz, Jan 28 2015