A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell.

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

Table of n, a(n) for n=0..17.

Ricardo Bittencourt, C++ code, GitHubGist.

Ricardo Bittencourt, Go code, GitHubGist.

OEIS Wiki: Self-avoiding walks

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.

Cf. A005773, A272469, A272763, A272773.

Sequence in context: A329764 A183411 A136778 * A278398 A356269 A000266

Adjacent sequences: A300662 A300663 A300664 * A300666 A300667 A300668

Keyword

nonn,walk,more

Author

Ricardo Bittencourt, Mar 10 2018

Status

approved