|
|
A326954
|
|
Numerator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.
|
|
3
|
|
|
1, 2, 23, 15, 2355, 1395, 102971, 58331, 16664147, 9197779, 160882675, 87300443, 48181451689, 25832538281, 881993826001, 468673213505, 508090131646771, 268129446332211, 4514206380211785, 2369170809554097, 317528931045821675
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The starting square is always considered part of the walk.
|
|
LINKS
|
|
|
EXAMPLE
|
a(0) = 1 (from 1/1), we count the starting square.
a(1) = 2 (from 2/1), each possible first step is unique.
a(2) = 23 (from 23/8), as for each possible first step 1/8th of the second steps go back to a previous square, thus the expected distinct squares visited is 2 + 7/8 = 23/8.
|
|
PROG
|
(Python3)
from itertools import product
from fractions import Fraction
def walk(steps):
s = [(0, 0)]
for dx, dy in steps:
s.append((s[-1][0] + dx, s[-1][1] + dy))
return s
moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
(2, 1), (2, -1), (-2, 1), (-2, -1)]
sum(len(set(walk(steps)))
for steps in product(moves, repeat=n)),
8**n
).numerator
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,frac,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|