|
|
A300665
|
|
Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.
|
|
2
|
|
|
1, 3, 15, 75, 391, 2065, 11091, 60215, 330003, 1820869, 10103153, 56313047, 315071801, 1768489771, 9953853677, 56158682949, 317505199769, 1798402412539
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
All terms are odd.
|
|
LINKS
|
Ricardo Bittencourt, C++ code, GitHubGist.
Ricardo Bittencourt, Go code, GitHubGist.
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=2, the a(2)=15 paths are:
.
. 0 . . 0 . . 0 . . 0 2 . 0 . .
. | | | |/ \
. 1 . . 1 . . 1-2 . 1 . . 2-1 .
. | \
. 2 . . . 2 . . . . . . . . . .
.
. 0 . . 0 . . 0 . . 0 . . 0 . 2
. \ \ \ \ \ /
. . 1 . . 1 . . 1 . . 1-2 . 1 .
. / | \
. 2 . . . 2 . . . 2 . . . . . .
.
. 0 2 . 0-1 . 0-1 . 0-1 . 0-1-2
. \| / | \
. . 1 . 2 . . . 2 . . . 2 . . .
.
. . . . . . . . . . . . . . . .
|
|
MATHEMATICA
|
next[x_]:=Map[x + #&, Tuples[{-1, 0, 1}, 2]]
valid[s_]:=Select[next[s[[-1]]], 0<=#[[1]] && 0<=#[[2]] && FreeQ[s, #] &]
nextpath[p_]:=Outer[Append, {p}, valid[p], 1]
iterate[p_]:=Flatten[Map[nextpath, p], 2]
Table[Length[Nest[iterate, {{{0, 0}}}, n-1]], {n, 1, 7}]
|
|
PROG
|
(C++) (see GitHubGist link)
(Go) (see GitHubGist link)
|
|
CROSSREFS
|
A038373 is the same process, but using only horizontal and vertical moves.
|
|
KEYWORD
|
nonn,walk,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|