login
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.
2
1, 2, 8, 40, 228, 1404, 9046, 59892, 403486, 2751104, 18928024, 131178640, 914753916, 6413644272, 45188265984, 319798943360, 2272481584604, 16209083200168, 116019175132958, 833115842931984, 6000491719051994, 43339577695514632, 313846571416413820
OFFSET
0,2
COMMENTS
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:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | |
+---+---+---+
A move consists of "sliding" a tile adjacent to the empty space into the empty space.
A parity argument shows that it is not possible for an odd number of moves to leave the state unchanged.
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).
LINKS
Sean A. Irvine, Java program (github)
Eric Weisstein's World of Mathematics, 15 Puzzle.
EXAMPLE
a(0)=1 because doing nothing leaves the puzzle in the identity state.
a(1)=2 because 66 and 88 leave the puzzle in the identity state (concatenating together the numbers moved to indicate the move sequence).
a(2)=8 by the sequences 6666, 6688, 8866, 8888, 6336, 8778, 6556, 8558.
More complicated move sequences occur for larger n.
CROSSREFS
Sequence in context: A337912 A085485 A089603 * A209358 A116456 A341876
KEYWORD
nonn
AUTHOR
Sean A. Irvine, Apr 06 2021
STATUS
approved