|
Search: id:A120399
|
|
|
| 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). |
|
+0
1
|
|
| 1, 0, 2, 2, 8, 4, 6, 108, 40, 20, 858, 252, 70, 5596, 1344, 252, 32814
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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.
|
|
FORMULA
|
Let K(n) equals 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: A021442 A093731 A049331 this_sequence A134812 A003612 A103839
Adjacent sequences: A120396 A120397 A120398 this_sequence A120400 A120401 A120402
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Sergey Perepechko (persn(AT)aport.ru), Jul 02 2006
|
|
|
Search completed in 0.002 seconds
|
