|
|
A025597
|
|
Number of n-move king paths on 8 X 8 board from given corner to opposite corner.
|
|
1
|
|
|
0, 0, 0, 0, 0, 0, 0, 1, 56, 1309, 20370, 255366, 2782296, 27630317, 256617790, 2269878170, 19345170656, 160223380546, 1297456951652, 10319966008680, 80906898257760, 626886465395595, 4810654849509082, 36623649326935517
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
As long as the path starts and ends on the correct square, it is counted. The path may revisit squares, including the start and end squares.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (4/81) * Sum_{j,k=1..8} (-1)^(j+k)* [sin(j*Pi/9)*sin(k*Pi/9)]^2 *[(1+2*cos(j*Pi/9))*(1+2*cos(k*Pi/9))-1]^n. - Andrew G. Buchanan, Jun 24 2012
G.f.: -(408459*x^21 +3108249*x^20 +5135985*x^19 -8733022*x^18 -29723403*x^17 -6771900*x^16 +52706117*x^15 +58351590*x^14 -6069219*x^13 -51965240*x^12 -37661505*x^11 -6328524*x^10 +5718540*x^9 +3500727*x^8 +471552*x^7 -208258*x^6 -90243*x^5 -9609*x^4 +1531*x^3 +498*x^2 +42*x+1) *x^7 / ((3*x-1) *(x+1) *(3*x^3-3*x-1) *(x^3-3*x+1) *(17*x^3+6*x^2-3*x-1) *(x^3+3*x^2-6*x+1) *(3*x^3+9*x^2+6*x-1) *(19*x^3-9*x^2-3*x+1) *(x^3+9*x^2+6*x+1) *(3*x^3-9*x^2-3*x+1) *(17*x^3+18*x^2+3*x-1)). - Alois P. Heinz, Jun 25 2012
|
|
EXAMPLE
|
The king cannot reach the opposite corner in fewer than 7 moves, hence a(0) through a(6) are all 0.
There is only one way to reach the opposite corner in 7 moves, namely along the main diagonal, so a(7) = 1.
|
|
MAPLE
|
b:= proc(n, i, j) option remember;
`if`(n<0 or i<0 or i>7 or j<0 or j>7, 0, `if`([n, i, j]=[0$3],
1, add(b(n-1, i+r[1], j+r[2]), r=[[1, 1], [1, 0], [1, -1],
[0, 1], [0, -1], [-1, 1], [-1, 0], [-1, -1]])))
end:
a:= n-> b(n, 7, 7):
|
|
MATHEMATICA
|
f[n_] := Round[4/81*Sum[(-1)^(j + k)*Sin[j*Pi/9]^2 Sin[k*Pi/9]^2*((1 + 2Cos[j*Pi/9])*(1 + 2Cos[k*Pi/9]) - 1)^n, {j, 8}, {k, 8}]]; Array[f, 23] (* Robert G. Wilson v, Jun 28 2012 *)
b[n_, i_, j_] := b[n, i, j] = If[n<0 || i<0 || i>7 || j<0 || j>7, 0, If[{n, i, j} == {0, 0, 0}, 1, Sum [b[n-1, i+r[[1]], j+r[[2]]], {r, {{1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}}}]]]; a[n_] := b[n, 7, 7]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 28 2015, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|