login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A300665 Number of n-step paths made by a chess king, starting from the corner of an infinite chessboard, and never revisiting a cell. 0
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

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

R. Bittencourt, C++ code, GitHubGist.

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

Sequence in context: A005053 A183411 A136778 * A278398 A000266 A294340

Adjacent sequences:  A300662 A300663 A300664 * A300666 A300667 A300668

KEYWORD

nonn,walk,more

AUTHOR

Ricardo Bittencourt, Mar 10 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 04:19 EDT 2018. Contains 302984 sequences. (Running on oeis4.)