A326954 - OEIS

%I #16 Nov 15 2024 19:53:33

%S 1,2,23,15,2355,1395,102971,58331,16664147,9197779,160882675,87300443,

%T 48181451689,25832538281,881993826001,468673213505,508090131646771,

%U 268129446332211,4514206380211785,2369170809554097,317528931045821675

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

%C The starting square is always considered part of the walk.

%H Math StackExchange, <a href="https://math.stackexchange.com/a/3312917/5558">Relatively efficient program to compute a(n) for larger n</a>.

%e a(0) = 1 (from 1/1), we count the starting square.

%e a(1) = 2 (from 2/1), each possible first step is unique.

%e 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 (Python)

%o from itertools import product

%o from fractions import Fraction

%o def walk(steps):

%o     s = [(0, 0)]

%o     for dx, dy in steps:

%o         s.append((s[-1][0] + dx, s[-1][1] + dy))

%o     return s

%o moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),

%o          (2, 1), (2, -1), (-2, 1), (-2, -1)]

%o A326954 = lambda n: Fraction(

%o         sum(len(set(walk(steps)))

%o             for steps in product(moves, repeat=n)),

%o         8**n

%o     ).numerator

%Y See A326955 for denominators. Cf. A309221.

%K nonn,frac,walk

%O 0,2

%A _Orson R. L. Peters_, Aug 08 2019