Imagine a simple sliding puzzle with three pieces on the vertices of a tetrahedron, that you can slide around along the edges. There are 24 possible game states. All moves in the game are recorded in the depicted graph, known as the Nauru graph.
Larger sliding puzzles with more “holes” can have even more interesting graphs. You can find a couple of examples here. There is among others a quite innocent-looking puzzle with five pieces and one hole, resulting in a subdivision of the truncated cuboctahedron with a total of 120 vertices!
In mathematics, a permutation group is a group G whose elements are permutations of a given set M, and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself); the relationship is often written as (G,M). Note that the group of all permutations of a set is the symmetric group; the term permutation group is usually restricted to mean a subgroup of the symmetric group. The symmetric group of n elements is denoted by Sn; if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M).
The application of a permutation group to the elements being permuted is called its group action; it has applications in both the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry.
Let me just preface this post by saying I have zero spatial skills. None at all. I am unable to turn things around in my head-- when I use a map, I need to hold it so it's aligned with the direction I'm facing. I can't rotate spheres, imagine flips, piece together a 3d cube from separate 2d images... it's all a struggle. (It's the main reason why I disliked R3 multivariable calculus so much. Just give me Rn where no one can visualise anything so I am not handicapped.)
As such, flips and rotations were things that I had a nebulous and shaky idea about. I knew vaguely that flipping then rotating a shape would give a different configuration than rotating and then flipping, but I had no concrete way of thinking about them. Hello group theory, I love you.
Here's the problem: how do we describe physical transformations of regular/symmetric shapes? Like flips and rotations of an equilateral triangle, or a square, or any polygon that's equiangular and equilateral? Here's the idea: label the vertices and track them as you move them. Let's do an example with a square:
We start with a square labelled counterclockwise, starting in the top left corner. First we rotated the square once clockwise (noticing rotating clockwise once is the same as rotating counterclockwise three times, so we will get the same configurations independently of which direction we choose, as long as we stick to that particular direction. I picked clockwise because it's my blog and I get to do what I want, dammit). Then, we did a horizontal flip along a vertical line of symmetry. The configuration we get is the same configuration we would have gotten if we had just done a diagonal flip to begin with.
The convenient thing about labelling axes is we can think of these physical manipulations, like flips and rotations, simply as permutations. For example, in the first rotation pictured, it took 1 to 4, 2 to 1, 3 to 2, and 4 to 3. In cycle notation, the permutation is (1, 4, 3, 2). The horizontal flip, as pictured, is similarly (1, 4)(2, 3). If we did the permutation composition of these two actions, we'd get (1, 4)(2, 3)(1, 4, 3, 2) = (2, 4) which is precisely the diagonal flip we ended up with.
So we see now that all the manipulations of actions on a square (or any regular polygon) will be a subgroup of a symmetric group. This representation gives suckers like me with no spatial talents a really nice, rigourous, and blessedly easy way to think about flipping and rotating things. The beauty is that we can use both the geometrical/physical representation and the permutation group representation together to make some observations about this group of manipulations.
The first thing to notice is that, given an n-gon, there are n-1 separate rotations. If we call the "smallest" rotation r, we get all the other rotations by just repeating r. Wala! The set of rotations is cyclic, and we get it with r as the generator. Notice rn is just the same as not having rotated the shape at all--the identity. Additionally, r can be represented as (1, n, n-1, n-2, ..., 3, 2) in terms of permutation notation.
With an n-gon, there are n possible flips. Geometrically, it's pretty easy to see that doing a flip twice undoes the flip, so the square of all flip permutations is the identity. As such, it's apparent that flips are just the composition of disjoint transpositions. These transpositions are composed pretty carefully/specifically since we're working around the structure of the shape (so we can't just pick two transpositions and stick them together).
Two cool results: the first is that we can get all possible flips from just a single flip and the set of rotations. Another way to put it is that the permutation group of manipulations on any shape is generated by <r, f>, where f is any flip. All n flips are generated with rkf, where k goes from 0 to n-1.
The second result is that rn/2 is the only non-identity element in the group that will commute with the other group elements. As someone with no spatial skills, this kind of result is one that I would have a lot of trouble producing or proving without permutation group theory/representation.
The group of manipulations on an n-gon is called the nth dihedral group, and it is isomorphic to a subgroup of the symmetric group on n letters.
Tangentially related, there's a delightful/frivolous little discussion on group theory and flipping things in a book by Brian Hayes entitled Group Theory in the Bedroom; the relevant chapter is online here. Only mathematicians would consider getting married to create more complex mathematical problems.
In abstract algebra, apermutation groupis a group \( G\) that consists in all possible permutations of a set. So to say, the elements of a permutation group are the possible permutations of the elements of a different, \( H\) group. Then we get a group \(\left( G,+\right)\) where \( +\) is the composition of permutations. Also, each permutation \(\phi_{i}\left(H\right)\) . We can assume that permutations are bijective functions, since as a group under composition of permutations, an inverse permutation that yields the identity permutation when composed with one specific permutation exists within \( G\) .
But how is the Rubik's 3x3 cube a permutation group?
Let's talk about the cube itself, disregarding the colors from now. The cube has six fixed piecesand 20 permutable pieces, therefore, every piece itself can be placed in \( 20!\) different positions. Hence, the Rubik's Cube pieces form an order 20! permutation group. But why would we even care on a rubiks cube without distinction of sides. Even a rock would solve one of those.
The cube WITH face distinction is another permutation group, over a greater set \(\bar{H}\) , this set is not formed by the pieces, but by the stickers on the pieces. The mathematics yielding this are slightly more complex, but the number of possible permutations without disassembling the cube is \( 8!\times 3^{7}\times 12!/2\times 2^{11}\). So we have a permutation group on this order. The fact scrambling and solvingn the cube shows the existence of inverse permutations, let's say that the solved cube is the identity permutation, the resut of that scramble is \(\psi\left( \bar{H}\right)\) and, the permutation that solves the cube would be \(\psi^{-1}\left( \bar{H}\right)\). But \(\psi^{-1}\) can be expressed as the composition of multiple, elemental permutations, which would be, face rotations. Which means that\(\psi^{-1}\left(\bar{H}\right) =\sum_{i=1}^{12}\alpha_{j}\varphi_{i} (\bar{H} )\) where \(\varphi_{i} (\bar{H} )\) are the single step face rotations and \(\alpha\in \{ 1,2,3\}\) since one-face rotations form cyclic subgroups of our permutation group \( G\) and the fourth rotation is equal to the identity rotation which is, not rotating the face at all. The single face rotations that \(\varphi_{i}\) represent are the steps in the solution of the cube.
---
Yes, this is pretty much something I will need to show my abstract Algebra I groub by the end of the semester.
