cp's OEIS Frontend

A343146 Number of move sequences of length 2n on the "8 Puzzle" which leave the final state unchanged when the empty cell starts in a corner.

%I A343146 #18 Feb 16 2025 08:34:01
%S A343146 1,2,8,40,228,1404,9046,59892,403486,2751104,18928024,131178640,
%T A343146 914753916,6413644272,45188265984,319798943360,2272481584604,
%U A343146 16209083200168,116019175132958,833115842931984,6000491719051994,43339577695514632,313846571416413820
%N A343146 Number of move sequences of length 2n on the "8 Puzzle" which leave the final state unchanged when the empty cell starts in a corner.
%C A343146 The "8 Puzzle" is the 3 X 3 analog of the "15 Puzzle". This sequence counts the possible move sequences of length 2n which leaves the puzzle in an unchanged state when starting from the following state:
%C A343146   +---+---+---+
%C A343146   | 1 | 2 | 3 |
%C A343146   +---+---+---+
%C A343146   | 4 | 5 | 6 |
%C A343146   +---+---+---+
%C A343146   | 7 | 8 |   |
%C A343146   +---+---+---+
%C A343146 A move consists of "sliding" a tile adjacent to the empty space into the empty space.
%C A343146 A parity argument shows that it is not possible for an odd number of moves to leave the state unchanged.
%C A343146 Unlike A046164, a given state (including the start state) is allowed to repeat an arbitrary number of times in a given move sequence (e.g., repeatedly moving a number backward or forward is permitted).
%H A343146 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a343/A343146.java">Java program</a> (github)
%H A343146 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/15Puzzle.html">15 Puzzle.</a>
%e A343146 a(0)=1 because doing nothing leaves the puzzle in the identity state.
%e A343146 a(1)=2 because 66 and 88 leave the puzzle in the identity state (concatenating together the numbers moved to indicate the move sequence).
%e A343146 a(2)=8 by the sequences 6666, 6688, 8866, 8888, 6336, 8778, 6556, 8558.
%e A343146 More complicated move sequences occur for larger n.
%Y A343146 Cf. A046164, A089473.
%K A343146 nonn
%O A343146 0,2
%A A343146 _Sean A. Irvine_, Apr 06 2021