Permutation Groups

Entire books have been written on the theory of the mathematical structures known as groups. However, our study of Pólya's enumeration theorem requires only a few facts about a particular class of groups that we introduce in this section. First, recall that a bijection from a set \(X\) to itself is called a permutation. A permutation group is a set \(P\) of permutations of a set \(X\) so that

1. \(\iota\)\(P\)
2. \(\pi_1,\pi_2\in P\)\(\pi_2\circ \pi_1\in P\)
3. \(\pi_1\in P\)\(\pi_1\inv\in P\)

As our first example of a permutation group, consider the set of permutations we discussed in , called the dihedral group of the square. We will denote this group by \(D_8\). We denote by \(D_{2n}\) the similar group of transformations for a regular \(n\)-gon, using \(2n\) as the subscript because there are \(2n\) permutations in this group.Some authors and computer algebra systems use \(D_n\) as the notation for the dihedral group of the \(n\)-gon. The first criterion to be a permutation group is clearly satisfied by \(D_8\). Verifying the other two is quite tedious, so we only present a couple of examples. First, notice that \(r_2\circ r_1=r_3\). This can be determined by carrying out the composition of these functions as permutations or by noting that rotating \(90^\circ\) clockwise and then \(180^\circ\) clockwise is the same as rotating \(270^\circ\) clockwise. For \(v\circ r\), we find \(v\circ r(1) = 1\), \(v\circ r(3)=3\), \(v\circ r(2)=4\), and \(v\circ r(4)=2\), so \(v\circ r=n\). For inverses, we have already discussed that \(r_1\inv = r_3\). Also, \(v\inv = v\), and more generally, the inverse of any flip is that same flip.

The way a permutation rearranges the elements of \(X\) is central to Pólya's enumeration theorem. A proper choice of representation for a permutation is very important here, so let's discuss how permutations can be represented. One way to represent a permutation \(\pi\) of \([n]\) is as a \(2\times n\) matrix in which the first row represents the domain and the second row represents \(\pi\) by putting \(\pi(i)\) in position \(i\). For example, \[\begin{aligned}\end{aligned}\] is the permutation of \([5]\) with \(\pi(1) =2\), \(\pi(2)=4\), \(\pi(3)=3\), \(\pi(4) = 5\), and \(\pi(5) = 1\). This notation is rather awkward and provides only the most basic information about the permutation. A more compact (and more useful for our purposes) notation is known as cycle notation. One way to visualize how the cycle notation is constructed is by constructing a digraph from a permutation \(\pi\) of \([n]\). The digraph has \([n]\) as its vertex set and a directed edge from \(i\) to \(j\) if and only if \(\pi(i) = j\). (Here we allow a directed edge from a vertex to itself if \(\pi(i) = i\).) The digraph corresponding to the permutation \(\pi\) from above is shown in .

Since \(\pi\) is a permutation, every component of such a digraph is a directed cycle. We can then use these cycles to write down the permutation in a compact manner. For each cycle, we start at the vertex with smallest label and go around the cycle in the direction of the edges, writing down the vertices' labels in order. We place this sequence of integers in parentheses. For the \(4\)-cycle in , we thus obtain \((1245)\). (If \(n\geq 10\), we place spaces or commas between the integers.) The component with a single vertex is denoted simply as \((3)\), and thus we may write \(\pi=(1245)(3)\). By convention, the disjoint cycles of a permutation are listed so that their first entries are in increasing order.

Because the operation in an arbitrary group is frequently called multiplication, it is common to refer to the composition of permutations as multiplication and write \(\pi_2\pi_1\) instead of \(\pi_2\circ \pi_1\). The important thing to remember here, however, is that the operation is simply function composition. Let's see a couple of examples.

It quickly gets tedious to write down where the product of two (or more) permutations sends each element. A more efficient approach would be to draw the digraph and then write down the cycle structure. With some practice, however, you can build the cycle notation as you go along, as we demonstrate in the following example.

We conclude this section with one more example.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.