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
the identity permutation \(\iota\) is in \(P\text{;}\)
if \(\pi_1,\pi_2\in P\text{,}\) then \(\pi_2\circ \pi_1\in P\text{;}\) and
if \(\pi_1\in P\text{,}\) then \(\pi_1\inv\in P\text{.}\)
For our purposes, \(X\) will always be finite and we will usually take \(X=[n]\) for some positive integer \(n\text{.}\) The symmetric group on \(n\) elements, denoted \(S_n\text{,}\) is the set of all permutations of \([n]\text{.}\) Every finite permutation group (and more generally every finite group) is a subgroup of \(S_n\) for some positive integer \(n\text{.}\)
As our first example of a permutation group, consider the set of permutations we discussed in Section 15.1, called the dihedral group of the square. We will denote this group by \(D_8\text{.}\) 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. 1
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\text{.}\) 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\text{.}\) 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\text{,}\) we find \(v\circ r(1) = 1\text{,}\)\(v\circ r(3)=3\text{,}\)\(v\circ r(2)=4\text{,}\) and \(v\circ r(4)=2\text{,}\) so \(v\circ r=n\text{.}\) For inverses, we have already discussed that \(r_1\inv = r_3\text{.}\) Also, \(v\inv = v\text{,}\) and more generally, the inverse of any flip is that same flip.
Subsection15.2.1Representing permutations
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\text{.}\) For example,
is the permutation of \([5]\) with \(\pi(1) =2\text{,}\)\(\pi(2)=4\text{,}\)\(\pi(3)=3\text{,}\)\(\pi(4) = 5\text{,}\) and \(\pi(5) = 1\text{.}\) 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]\text{.}\) The digraph has \([n]\) as its vertex set and a directed edge from \(i\) to \(j\) if and only if \(\pi(i) = j\text{.}\) (Here we allow a directed edge from a vertex to itself if \(\pi(i) = i\text{.}\)) The digraph corresponding to the permutation \(\pi\) from above is shown in Figure 15.3.
Figure15.3.The digraph corresponding to permutation \(\pi=(1245)(3)\)
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 Figure 15.3, we thus obtain \((1245)\text{.}\) (If \(n\geq 10\text{,}\) we place spaces or commas between the integers.) The component with a single vertex is denoted simply as \((3)\text{,}\) and thus we may write \(\pi=(1245)(3)\text{.}\) By convention, the disjoint cycles of a permutation are listed so that their first entries are in increasing order.
Example15.4.
The permutation \(\pi=(1483)(27)(56)\) has \(\pi(1)=4\text{,}\)\(\pi(8)=3\text{,}\)\(\pi(3)=1\text{,}\) and \(\pi(5)=6\text{.}\) The permutation \(\pi'=(13)(2)(478)(56)\) has \(\pi'(1)=3\text{,}\)\(\pi'(2) = 2\text{,}\) and \(\pi'(8)=4\text{.}\) We say that \(\pi\) consists of two cycles of length \(2\) and one cycle of length \(4\text{.}\) For \(\pi'\text{,}\) we have one cycle of length \(1\text{,}\) two cycles of length \(2\text{,}\) and one cycle of length \(3\text{.}\) A cycle of length \(k\) will also called a \(k\)-cycle in this chapter.
Subsection15.2.2Multiplying permutations
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\text{.}\) The important thing to remember here, however, is that the operation is simply function composition. Let’s see a couple of examples.
Example15.5.
Let \(\pi_1 = (1234)\) and \(\pi_2 = (12)(34)\text{.}\) (Notice that these are the permutations \(r_1\) and \(v\text{,}\) respectively, from \(D_8\text{.}\)) Let \(\pi_3=\pi_2\pi_1\text{.}\) To determine \(\pi_3\text{,}\) we start by finding \(\pi_3(1) = \pi_2\pi_1(1) = \pi_2(2) = 1\text{.}\) We next find that \(\pi_3(2) = \pi_2\pi_1(2) = \pi_2(3)=4\text{.}\) Similarly, \(\pi_3(3) = 3\) and \(\pi_3(4)=2\text{.}\) Thus, \(\pi_3=(1)(24)(3)\text{,}\) which we called \(n\) earlier.
Now let \(\pi_4 = \pi_1\pi_2\text{.}\) Then \(\pi_4(1) = 3\text{,}\)\(\pi_4(2)=2\text{,}\)\(\pi_4(3)=1\text{,}\) and \(\pi_4(4)=4\text{.}\) Therefore, \(\pi_4=(13)(2)(4)\text{,}\) which we called \(p\) earlier. It’s important to note that \(\pi_1\pi_2\neq \pi_2\pi_1\text{,}\) which hopefully does not surprise you, since function composition is not in general commutative. To further illustrate the lack of commutativity in permutation groups, pick up a book (Not this one! You need to keep reading directions here.) so that cover is up and the spine is to the left. First, flip the book over from left to right. Then rotate it \(90^\circ\) clockwise. Where is the spine? Now return the book to the cover-up, spine-left position. Rotate the book \(90^\circ\) clockwise and then flip it over from left to right. Where is the spine this time?
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.
Example15.6.
Let \(\pi_1=(123)(487)(5)(6)\) and \(\pi_2=(18765)(234)\text{.}\) Let \(\pi_3 = \pi_2\pi_1\text{.}\) To start constructing the cycle notation for \(\pi_3\text{,}\) we must determine where \(\pi_3\) sends \(1\text{.}\) We find that it sends it to \(3\text{,}\) since \(\pi_1\) sends \(1\) to \(2\) and \(\pi_2\) sends \(2\) to \(3\text{.}\) Thus, the first cycle begins \(13\text{.}\) Now where is \(3\) sent? It’s sent to \(8\text{,}\) which goes to \(6\text{,}\) which goes to \(5\text{,}\) which goes to \(1\text{,}\) completing our first cycle as \((13865)\text{.}\) The first integer not in this cycle is \(2\text{,}\) which we use to start our next cycle. We find that \(2\) is sent to \(4\text{,}\) which is set to \(7\text{,}\) which is set to \(2\text{.}\) Thus, the second cycle is \((247)\text{.}\) Now all elements of \(8\) are represented in these cycles, so we know that \(\pi_3 = (13865)(247)\text{.}\)
We conclude this section with one more example.
Example15.7.
Let’s find \([(123456)][(165432)]\text{,}\) where we’ve written the two permutations being multiplied inside brackets. Since we work from right to left, we find that the first permutation applied sends \(1\) to \(6\text{,}\) and the second sends \(6\) to \(1\text{,}\) so our first cycle is \((1)\text{.}\) Next, we find that the product sends \(2\) to \(2\text{.}\) It also sends \(i\) to \(i\) for every other \(i\leq 6\text{.}\) Thus, the product is \((1)(2)(3)(4)(5)(6)\text{,}\) which is better known as the identity permutation. Thus, \((123456)\) and \((165432)\) are inverses.
In the next section, we will use standard counting techniques we’ve seen before in this book to prove results about groups acting ons ets. We will state the results for arbitrary groups, but you may safely replace “group” by “permutation group” without losing any understanding required for the remainder of the chapter.
