login
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
OFFSET
0,2
COMMENTS
All terms are odd.
LINKS
Ricardo Bittencourt, C++ code, GitHubGist.
Ricardo Bittencourt, Go code, GitHubGist.
FORMULA
a(n) = A272469(n) + 2*A005773(n+1) - 1 for n > 0. - Andrey Zabolotskiy, Mar 12 2018
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.
Sequence in context: A329764 A183411 A136778 * A278398 A356269 A000266
KEYWORD
nonn,walk,more
AUTHOR
Ricardo Bittencourt, Mar 10 2018
STATUS
approved