login
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
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
Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 49 terms from David W. Wilson)
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):
seq(a(n), n=0..30); # Alois P. Heinz, Jun 25 2012
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
Sequence in context: A183587 A219469 A278079 * A034202 A160290 A030649
KEYWORD
nonn,easy
EXTENSIONS
a(24)-a(48) from Wouter Meeussen, Jun 24 2012
STATUS
approved