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,3

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.

Links

Table of n, a(n) for n=1..39.

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

Example

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)

Crossrefs

Sequence in context: A369771 A239677 A331333 * A144816 A134812 A144847

Adjacent sequences: A120396 A120397 A120398 * A120400 A120401 A120402

Keyword

nonn

Author

Sergey Perepechko, Jul 02 2006

Extensions

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

Status

approved