login
Number of n-step self-avoiding walks on a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.
4

%I #17 Jan 26 2022 08:21:15

%S 1,4,12,36,92,252,628,1644,4052,10340,25332,63708,155452,387036,

%T 941948,2328740,5657236,13914596,33757804,82713164,200467108,

%U 489746916,1186060492,2891000036,6997192716,17025058164,41186981772,100070851212,242000513660,587312389940

%N Number of n-step self-avoiding walks on a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.

%C The number of the square ring around the origin the walk is currently on is just the maximum of the absolute values of its current x and y coordinates. In this sequence the SAW cannot step to a coordinate that has a smaller ring number than the ring it is currently on. For example, a step from (1,2) to either (2,2), (1,3), (0,2) is permitted as it stays on the second ring or steps to the third, but a step from (1,2) to (1,1) is forbidden as that would be stepping to the smaller first ring.

%e a(0..3) are the same as the standard square lattice SAW of A001411 as the walk cannot step to a smaller ring in the first three steps.

%e a(4) = 92. If we restrict the first one or more steps to the right followed by an upward step then there is one walk which steps to a smaller ring and is thus forbidden. That is the walk (0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1). As this can be walked in eight different ways on the square lattice the number of 4-step walks becomes A001411(4) - 8 = 100 - 8 = 92.

%Y Cf. A001411, A001333, A337353.

%K nonn,walk

%O 0,2

%A _Scott R. Shannon_, Sep 23 2021