cp's OEIS Frontend

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

%I A326954 #16 Nov 15 2024 19:53:33
%S A326954 1,2,23,15,2355,1395,102971,58331,16664147,9197779,160882675,87300443,
%T A326954 48181451689,25832538281,881993826001,468673213505,508090131646771,
%U A326954 268129446332211,4514206380211785,2369170809554097,317528931045821675
%N A326954 Numerator of the expected number of distinct squares visited by a knight's random walk on an infinite chessboard after n steps.
%C A326954 The starting square is always considered part of the walk.
%H A326954 Math StackExchange, <a href="https://math.stackexchange.com/a/3312917/5558">Relatively efficient program to compute a(n) for larger n</a>.
%e A326954 a(0) = 1 (from 1/1), we count the starting square.
%e A326954 a(1) = 2 (from 2/1), each possible first step is unique.
%e A326954 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.
%o A326954 (Python)
%o A326954 from itertools import product
%o A326954 from fractions import Fraction
%o A326954 def walk(steps):
%o A326954     s = [(0, 0)]
%o A326954     for dx, dy in steps:
%o A326954         s.append((s[-1][0] + dx, s[-1][1] + dy))
%o A326954     return s
%o A326954 moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
%o A326954          (2, 1), (2, -1), (-2, 1), (-2, -1)]
%o A326954 A326954 = lambda n: Fraction(
%o A326954         sum(len(set(walk(steps)))
%o A326954             for steps in product(moves, repeat=n)),
%o A326954         8**n
%o A326954     ).numerator
%Y A326954 See A326955 for denominators. Cf. A309221.
%K A326954 nonn,frac,walk
%O A326954 0,2
%A A326954 _Orson R. L. Peters_, Aug 08 2019