I'm trying to follow a text about Permutation Puzzles: A Mathematical Perspective but I'm getting into a real pickle when it comes to cycle notation and how it relates to permutations in the specific context of a simple puzzle where you swap numbers in an array-like structure.
What is confusing me is that the elements in permutations given in the text seem to change roles from referring to values vs positions, and vice versa, and I can't tell when each is the appropriate interpretation.
I've made myself a computer program to try to follow along and visualize/understand what I'm doing as I learn this subject.
In this example:
α = (1 5 3 7)(4 8 6) = (6 8)(5 7)(4 8)(3 7)(1 5)
To get the board configuration corresponding to (1 5 3 7)(4 8 6), I perform the following steps, where the numbers given refer to the VALUES on the tiles, not their positions.
- 1 swaps with 5
- 5 swaps with 3
- 3 swaps with 7
- 7 is already at position 1 so I don't swap. I notice here I am thinking in terms of position rather than value, here at the end of the cycle, and I don't know why...
- 4 swaps with 8
- 8 swaps with 6
- 6 is already at position 4 so I don't swap. I notice here I am thinking in terms of position rather than value, here at the end of the cycle, and I don't know why...
giving 7|2|5|6|1|8|3|4
Then I try to see how this is equivalent to (6 8)(5 7)(4 8)(3 7)(1 5)
On experimentation, it turns out that this second sequence needs to be interpreted with the numbers inside the 2-cycles referring to the POSITIONS, not the VALUES.
This strikes me as noteworthy, but I don't understand what I'm doing enough to draw any conclusions, so I press on...
Next I read
β = (1 5 3 4 2) = (1 5)(1 3)(1 4)(1 2)
It strikes me as strange that
β = (1 5 3 4 2) = (1 5)(1 3)(1 4)(1 2)
seems to represent
2|4|5|3|1|6|7|8
using the same "value swapping except for the last item in a cycle" approach as before, but in order to go from this state to the solved state (1|2|3|4|5|6|7|8), I need to interpret the numbers inside the permutation as representing VALUES as opposed to POSITIONS.
This seems to be the opposite of the case in the previous example.
Now it may be that β represents a completely different animal to α, in fact it says as much in the text:
Definition 5.1.1 — Puzzle Position → Permutation. For a given position (scrambling) of the puzzle, the permutation corresponding to this position is α : Sn → Sn where α(i) = j if the piece labelled i is in the position labelled j.
Definition 5.1.2 — Puzzle Move → Permutation. For a given move sequence applied to the puzzle, the permutation corresponding to this move sequence is β : Sn → Sn where β(i) = j if the piece in position labelled i moved to position labelled j.
However I don't have enough experience to be able to make sense of those definitions yet - that is what I'm trying to acquire by following along using my tile swapping program...
I'm hoping someone reading this will be able to recognise what is tripping me up in my understanding and provide clarification. The essence of my questions is when should I think "the value at position x" and when "the value y" when reasoning about permutations in cycle notation?