*Permutations* are bijective (one-to-one and onto) functions from a set to itself. When the set is {1, 2, …, *n*}, then its complete set of permutations is denoted by *S _{n}*, which is a group when composition of functions is taken as the operation.

**A fundamental fact:** *Every permutation in* *S _{n} can be expressed as the composition of a sequence of transpositions.
*

A

It is easy to see why the claim in the preceding paragraph is true if one thinks of representing permutations in *S _{n}* by using

One could equally well reverse the roles of marker numbers and box numbers in terms of which represents the domain and which the range variables. The representation set forth here reflects a tactile point of view. We think of a function as going *from* the domain *to* the range. Thus, we are interpreting a(*i*) *= j* as saying that the marker that originally came *from* box *i* has gone *to* box *j*.

If we think about permutations in this way, then a transposition (*a, b*) is a permutation represented by the swapping of the contents of two boxes, namely box *a* and box *b.* If we compose a sequence of transpositions, then we can represent this by a sequence of steps of swapping pairs of markers between boxes. It does not take very long doing this, or even just thinking about it, before one sees clearly that one can achieve any permutation one wants by a sequence of swaps of markers. Equivalently, one can easily see how one could restore each marker to its home box in Figure 1 by doing a sequence of swaps.