Permutations

A permutation is a rearrangement of objects. In this paper we will only consider permutations (rearrangements) of a finite number of objects, and since the object names don't really matter, we will often simply consider permutations of the numbers $1, 2, 3, \ldots, n$. When we work with Rubik's Cube, however, there are better names for the faces than integers--see Section 3.

Of course we'll learn about permutations first by looking at permutations of small numbers of items, but if you think of the 54 colored faces of the little cubelets (``cubies'') on Rubik's Cube, you can see that every time you twist a side of the cube, you are rearranging those little faces.

There are plenty of other examples of permutations, many of which are extremely important and practical. For example, when you have a list of items to sort, either by hand or with a computer program, you are essentially faced with the problem of finding a permutation of the objects that will put them in order after the permutation.

If we consider permutations of $n$ objects, there are $n!$ of them. To see this, first consider where object number 1 winds up. There are $n$ possibilities for that. After the fate of object 1 is determined, there are only $n-1$ possible fates for object number 2. Thus there are $n(n-1)(n-2)\cdots 3\cdot 2\cdot 1 = n!$ permutations of a set of $n$ objects.

For example, if we consider all possible rearrangements of the set $\{1, 2, 3\}$, there are $3! = 3\cdot 2\cdot 1 = 6$ of them, listed in Table 1.

Table 1: Permutations of 3 objects

$1$	$1\rightarrow 1$	$2\rightarrow 2$	$3\rightarrow 3$
$2$	$1\rightarrow 2$	$2\rightarrow 1$	$3\rightarrow 3$
$3$	$1\rightarrow 3$	$2\rightarrow 2$	$3\rightarrow 1$
$4$	$1\rightarrow 1$	$2\rightarrow 3$	$3\rightarrow 2$
$5$	$1\rightarrow 2$	$2\rightarrow 3$	$3\rightarrow 1$
$6$	$1\rightarrow 3$	$2\rightarrow 1$	$3\rightarrow 2$

A good way to think of permutations is this (using permutations of three objects as an example): Imagine that there are three boxes labelled ``1'', ``2'', and ``3'', and initially, each contains a ball labelled with the same number--box 1 contains ball 1, and so on. A permutation is a rearrangement of the balls but in such a way that when you're done there is still only a single ball in each box.

In the table above, the notation $a\rightarrow b$ indicates that whatever was in box $a$ moves to the box labelled $b$, so to apply permutation number 3 above means to take whatever ball is in box $1$ and move it to box $3$, to leave the contents of box $2$ alone, and to take the ball from box three and put it into box $1$. In other words, permutation number $3$ above tells us to swap the contents of boxes $1$ and $3$.

The notation above is pretty clumsy. Here are a couple of other possibilities: