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

Author

Ricardo Bittencourt, Mar 10 2018

Keywords

• nonn
• walk
• more

Comments

All terms are odd.

Examples

			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     . . .
.
.    . . .     . . .     . . .     . . .     . . .
		

Links

• Ricardo Bittencourt, C++ code, GitHubGist.
• Ricardo Bittencourt, Go code, GitHubGist.
• OEIS Wiki: Self-avoiding walks

Crossrefs

A038373 is the same process, but using only horizontal and vertical moves.

Cf. A005773, A272469, A272763, A272773.

Programs

Go

(see GitHubGist link)

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}]

Formula

a(n) = A272469(n) + 2*A005773(n+1) - 1 for n > 0. - Andrey Zabolotskiy, Mar 12 2018