

A326955


Denominator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.


3



1, 1, 8, 4, 512, 256, 16384, 8192, 2097152, 1048576, 16777216, 8388608, 4294967296, 2147483648, 68719476736, 34359738368, 35184372088832, 17592186044416, 281474976710656, 140737488355328, 18014398509481984
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The starting square is always considered part of the walk.


LINKS

Table of n, a(n) for n=0..20.
Math StackExchange, Relatively efficient program to compute a(n) for larger n.


EXAMPLE

a(0) = 1 (from 1/1), we count the starting square.
a(1) = 1 (from 2/1), each possible first step is unique.
a(2) = 8 (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

(Python)
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)]
A326955 = lambda n: Fraction(
sum(len(set(walk(steps)))
for steps in product(moves, repeat=n)),
8**n
).denominator


CROSSREFS

See A326954 for numerators. Cf. A309221.
Sequence in context: A268482 A231234 A096687 * A199374 A289538 A154224
Adjacent sequences: A326952 A326953 A326954 * A326956 A326957 A326958


KEYWORD

nonn,frac,walk


AUTHOR

Orson R. L. Peters, Aug 08 2019


STATUS

approved



