cp's OEIS Frontend

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

%I A326955 #11 Aug 28 2019 18:28:45
%S A326955 1,1,8,4,512,256,16384,8192,2097152,1048576,16777216,8388608,
%T A326955 4294967296,2147483648,68719476736,34359738368,35184372088832,
%U A326955 17592186044416,281474976710656,140737488355328,18014398509481984
%N A326955 Denominator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.
%C A326955 The starting square is always considered part of the walk.
%H A326955 Math StackExchange, <a href="https://math.stackexchange.com/a/3312917/5558">Relatively efficient program to compute a(n) for larger n</a>.
%e A326955 a(0) = 1 (from 1/1), we count the starting square.
%e A326955 a(1) = 1 (from 2/1), each possible first step is unique.
%e A326955 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.
%o A326955 (Python)
%o A326955 from itertools import product
%o A326955 from fractions import Fraction
%o A326955 def walk(steps):
%o A326955     s = [(0, 0)]
%o A326955     for dx, dy in steps:
%o A326955         s.append((s[-1][0] + dx, s[-1][1] + dy))
%o A326955     return s
%o A326955 moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
%o A326955          (2, 1), (2, -1), (-2, 1), (-2, -1)]
%o A326955 A326955 = lambda n: Fraction(
%o A326955         sum(len(set(walk(steps)))
%o A326955             for steps in product(moves, repeat=n)),
%o A326955         8**n
%o A326955     ).denominator
%Y A326955 See A326954 for numerators. Cf. A309221.
%K A326955 nonn,frac,walk
%O A326955 0,3
%A A326955 _Orson R. L. Peters_, Aug 08 2019