Until now we have thought of permutations mostly as ways of listing the elements of a set. In this chapter we will find it very useful to think of permutations as functions. This will help us in using permutations to solve enumeration problems that cannot be solved by the quotient principle because they involve counting the blocks of a partition in which the blocks don't have the same size. We begin by studying the kinds of permutations that arise in situations where we have used the quotient principle in the past.
In Figure 6.1.1 we show a square with its four vertices labelled 1, 2, 3, and 4. We have also labeled the spot in the plane where each of these vertices falls with the same label. Then we have shown the effect of rotating the square clockwise through 90, 180, 270, and 360 degrees (which is the same as rotating through 0 degrees). Underneath each of the rotated squares we have named the function that carries out the rotation. We use \(\rho\text{,}\) the Greek letter pronounced “row,” to stand for a 90 degree clockwise rotation. We use \(\rho^2\) to stand for two 90 degree rotations, and so on. We can think of the function \(\rho\) as a function on the four element set 1 What we are doing is restricting the rotation \(\rho\) to the set \(\{1,2,3,4\}\text{.}\) \(\{1,2,3,4\}\text{.}\) In particular, for any function \(\varphi\) (the Greek letter phi, usually pronounced “fee,” but sometimes “fie”) from the plane back to itself that may move the square around but otherwise leaves it in the same place, we let \(\varphi(i)\) be the label of the place where vertex previously in position \(i\) is now. Thus \(\rho(1) =2\text{,}\) \(\rho(2)=3\text{,}\) \(\rho(3)=4\) and \(\rho(4) =1\text{.}\) Notice that \(\rho\) is a permutation on the set \(\{1,2,3,4\}\text{.}\)
The composition \(f\circ g\) of two functions \(f\) and \(g\) is defined by \(f\circ g(x) = f(g(x))\text{.}\) Is \(\rho^3\) the composition of \(\rho\) and \(\rho^2\text{?}\) Does the answer depend on the order in which we write \(\rho\) and \(\rho^2\text{?}\) How is \(\rho^2\) related to \(\rho\text{?}\)
Is the composition of two permutations always a permutation?
In Problem 248 you see that we can think of \(\rho^2\circ\rho\) as the result of first rotating by 90 degrees and then by another 180 degrees. In other words, the composition of two rotations is the same thing as first doing one and then doing the other. Of course there is nothing special about 90 degrees and 180 degrees. As long as we first do one rotation through a multiple of 90 degrees and then another rotation through a multiple of 90 degrees, the composition of these rotations is a rotation through a multiple of 90 degrees.
If we first rotate by 90 degrees and then by 270 degrees then we have rotated by 360 degrees, which does nothing visible to the square. Thus we say that \(\rho^4\) is the “identity function.” In general the identity function on a set \(S\text{,}\) denoted by \(\iota\) (the Greek letter iota, pronounced eye-oh-ta) is the function that takes each element of the set to itself. In symbols, \(\iota(x) =x\) for every \(x\) in \(S\text{.}\) Of course the identity function on a set is a permutation of that set.
For any function \(\varphi\) from a set \(S\) to itself, we define \(\varphi^n\) (for nonnegative integers \(n\)) inductively by \(\varphi^0 = \iota\) and \(\varphi^n = \varphi^{n-1}\circ\varphi\) for every positive integer \(n\text{.}\) If \(\varphi\) is a permutation, is \(\varphi^n\) a permutation? Based on your experience with previous inductive proofs, what do you expect \(\varphi^n\circ \varphi^m\) to be? What do you expect \((\varphi^m)^n\) to be? There is no need to prove these last two answers are correct, for you have, in effect, already done so in Chapter 2.
If we perform the composition \(\iota\circ \varphi\) for any function \(\varphi\) from \(S\) to \(S\text{,}\) what function do we get? What if we perform the composition \(\varphi\circ\iota\text{?}\)
What you have observed about iota in Problem 251 is called the identity property of iota. In the context of permutations, people usually call the function \(\iota\) “the identity” rather than calling it “iota.”
Since rotating first by 90 degrees and then by 270 degrees has the same effect as doing nothing, we can think of the 270 degree rotation as undoing what the 90 degree rotation does. For this reason we say that in the rotations of the square, \(\rho^3\) is the “inverse” of \(\rho\text{.}\) In general, a function \(\varphi:T\rightarrow S\) is called an inverse of a function \(\sigma:S \rightarrow T\) (the lower case Greek letter sigma) if \(\varphi\circ \sigma= \sigma \circ\varphi = \iota\text{.}\) For a slower introduction to inverses and practice with them, see Section A.1.3 in Appendix A. Since a permutation is a bijection, it has a unique inverse, as in Section A.1.3. And since the inverse of a bijection is a bijection (again, as in the Appendix), the inverse of a permutation is a permutation.
We use \(\varphi^{-1}\) to denote the inverse of the permutation \(\varphi\text{.}\) We've seen that the rotations of the square are functions that return the square to its original position but may move the vertices to different places. In this way we create permutations of the vertices of the square. We've observed three important properties of these permutations.
(Identity Property) These permutations include the identity permutation.
(Inverse Property) Whenever these permutations include \(\varphi\text{,}\) they also include \(\varphi^{-1}\text{.}\)
(Closure Property) Whenever these permutations include \(\varphi\) and \(\sigma\text{,}\) they also include \(\varphi\circ\sigma\text{.}\)
A set of permutations with these three properties is called a permutation group 2 The concept of a permutation group is a special case of the concept of a group that one studies in abstract algebra. When we refer to a group in what follows, if you know what groups are in the more abstract sense, you may use the word in this way. If you do not know about groups in this more abstract sense, then you may assume we mean permutation group when we say group. or a group of permutations. We call the group of permutations corresponding to rotations of the square the rotation group of the square. There is a similar rotation group with \(n\) elements for any regular \(n\)-gon.
If \(f:S\rightarrow T\text{,}\) \(g:T\rightarrow X\text{,}\) and \(h:X \rightarrow Y\text{,}\) is \(h\circ(g\circ f) = (h\circ g)\circ f\text{?}\) What does this say about the status of the associative law
in a group of permutations?
How should we define \(\varphi^{-n}\) for an element \(\varphi\) of a permutation group?
What do you want \(\varphi^n\circ\varphi^{-1}\) to be?
Will the two standard rules for exponents
still hold if one or more of the exponents may be negative?
What would we have to prove to show that the rules still hold?
If the rules hold, give enough of the proof to show that you know how to do it; otherwise give a counterexample.
If a finite set of permutations satisfies the closure property is it a permutation group?
If \(\sigma^i = \sigma^j\) and \(i \ne j\text{,}\) what can you conclude about \(\iota\text{?}\)
There are three-dimensional geometric motions of the square that return it to its original position but move some of the vertices to other positions. For example, if we flip the square around a diagonal, most of it moves out of the plane during the flip, but the square ends up in the same place. Draw a figure like Figure 6.1.1 that shows all the possible results of such motions, including the ones shown in Figure 6.1.1. Do the corresponding permutations form a group?
Let \(\sigma\) and \(\varphi\) be permutations.
Why must \(\sigma\circ\varphi\) have an inverse?
Is \((\sigma\circ\varphi)^{-1}=\sigma^{-1}\varphi^{-1}\text{?}\) (Prove or give a counter-example.)
What does it mean for one function to be the inverse of another one?
Is \((\sigma\circ\varphi)^{-1}= \varphi^{-1}\sigma^{-1}\text{?}\) (Prove or give a counter-example.)
Explain why the set of all permutations of four elements is a permutation group. How many elements does this group have? This group is called the symmetric group on four letters and is denoted by \(S_4\text{.}\)
In general, the set of all permutations of an \(n\)-element set is a group. It is called the symmetric group on \(n\) letters. We don't have nice geometric descriptions (like rotations) for all its elements, and it would be inconvenient to have to write down something like “Let \(\sigma(1) =3\text{,}\) \(\sigma(2) =1\text{,}\) \(\sigma(3)=4\text{,}\) and \(\sigma(4)=1\)” each time we need to introduce a new permutation. We introduce a new notation for permutations that allows us to denote them reasonably compactly and compose them reasonably quickly. If \(\sigma\) is the permutation of \(\{1,2,3,4\}\) given by \(\sigma(1)=3\text{,}\) \(\sigma(2)=1\text{,}\) \(\sigma(3) =4\) and \(\sigma(4) =2\text{,}\) we write
We call this notation the two row notation for permutations. In the two row notation for a permutation of \(\{a_1,a_2,\ldots, a_n\}\text{,}\) we write the numbers \(a_1\) through \(a_n\) in a one row and we write \(\sigma(a_1)\) through \(\sigma(a_n)\) in a row right below, enclosing both rows in parentheses. Notice that
although the second ordering of the columns is rarely used.
If \(\varphi\) is given by
then, by applying the definition of composition of functions, we may compute \(\sigma\circ \varphi\) as shown in Figure 6.1.2.
We don't normally put the circle between two permutations in two row notation when we are composing them, and refer to the operation as multiplying the permutations, or as the product of the permutations. To see how Figure 6.1.2 illustrates composition, notice that the arrow starting at 1 in \(\varphi\) goes to 4. Then from the 4 in \(\varphi\) it goes to the 4 in \(\sigma\) and then to 2. This illustrates that \(\varphi(1)=4\) and \(\sigma(4) =2\text{,}\) so that \(\sigma(\varphi(1))=2\text{.}\)
For practice, compute \(\begin{pmatrix}1\amp 2\amp 3\amp 4\amp 5\cr3\amp 4\amp 1\amp 5\amp 2 \end{pmatrix} \begin{pmatrix}1\amp 2\amp 3\amp 4\amp 5\cr 4\amp 3\amp 5\amp 1\amp 2 \end{pmatrix}\text{.}\)
We found four permutations that correspond to rotations of the square. In Problem 255 you found four permutations that correspond to flips of the square in space. One flip fixes the vertices in the places labeled 1 and 3 and interchanges the vertices in the places labeled 2 and 4. Let us denote it by \(\varphi_{1|3}\text{.}\) One flip fixes the vertices in the positions labeled 2 and 4 and interchanges those in the positions labeled 1 and 3. Let us denote it by \(\varphi{2|4}\text{.}\) One flip interchanges the vertices in the places labeled 1 and 2 and also interchanges those in the places labeled 3 and 4. Let us denote it by \(\varphi_{12|34}\text{.}\) The fourth flip interchanges the vertices in the places labeled 1 and 4 and interchanges those in the places labeled 2 and 3. Let us denote it by \(\varphi_{14|23}\text{.}\) Notice that \(\varphi_{1|3}\) is a permutation that takes the vertex in place 1 to the vertex in place 1 and the vertex in place 3 to the vertex in place 3, while \(\varphi_{12|34}\) is a permutation that takes the edge between places 1 and 2 to the edge between places 2 and 1 (which is the same edge) and takes the edge between places 3 and 4 to the edge between places 4 and 3 (which is the same edge). This should help to explain the similarity in the notation for the two different kinds of flips.
Write down the two-row notation for \(\rho^3\text{,}\) \(\varphi_{2|4}\text{,}\) \(\varphi_{12|34}\) and \(\varphi_{2|4}\circ \varphi_{12|34}\text{.}\) Remember that \(\sigma(i)\) stands for the position where the vertex that originated in position \(i\) is after we apply \(\sigma\text{.}\)
(You may have already done this problem in Problem 255, in which case you need not do it again!) In Problem 255, if a rigid motion of three-dimensional space returns the square to its original position, in how many places can vertex number one land? Once the location of vertex number one is decided, how many possible locations are there for vertex two? Once the locations of vertex one and vertex two are decided, how many locations are there for vertex three? Answer the same question for vertex four. What does this say about the relationship between the four rotations and four flips described above and the permutations you described in Problem 255?
The four rotations and four flips of the square described before Problem 259 form a group called the dihedral group of the square. Sometimes the group is denoted \(D_8\) because it has eight elements, and sometimes the group is denoted by \(D_4\) because it deals with four vertices! Let us agree to use the notation \(D_4\) for the dihedral group of the square. There is a similar dihedral group, denoted by \(D_{n}\text{,}\) of all the rigid motions of three-dimensional space that return a regular \(n\)-gon to its original position (but might put the vertices in different places.)
Another view of the dihedral group of the square is that it is the group of all distance preserving functions, also called isometries, from a square to itself. Notice that an isometry must be a bijection. Any rigid motion of the square preserves the distances between all points of the square. However, it is conceivable that there might be some isometries that do not arise from rigid motions. (We will see some later on in the case of a cube.) Show that there are exactly eight isometires (distance preserving functions) from a square to itself.
Once you know where the corners of the square go under the action of an isometry, how much do you know about the isometry?
How many elements does the group \(D_n\) have? Prove that you are correct.
In Figure 6.1.3 we show a cube with the positions of its vertices and faces labeled. As with motions of the square, we let \(\varphi(x)\) be the label of the place where vertex previously in position \(x\) is now.
Write in two row notation the permutation \(\rho\) of the vertices that corresponds to rotating the cube 90 degrees around a vertical axis through the faces \(t\) (for top) and \(u\) (for underneath). (Rotate in a right-handed fashion around this axis, meaning that vertex 6 goes to the back and vertex 8 comes to the front.)
Write in two row notation the permutation \(\varphi\) that rotates the cube 120 degrees around the diagonal from vertex 1 to vertex 7 and carries vertex 8 to vertex 6.
Compute the two row notation for \(\rho \circ \varphi\)
Is the permutation \(\rho\circ\varphi\) a rotation of the cube around some axis? If so, say what the axis is and how many degrees we rotate around the axis. If \(\rho\circ\varphi\) is not a rotation, give a geometic description of it.
How many permutations are in the group \(R\text{?}\) \(R\) is sometimes called the “rotation group” of the cube. Can you justify this?
In how many ways can you choose a place to which you can move vertex 1? Having done that, in how many ways can you place the three vertices adjacent to vertex 1?
As with a two-dimensional figure, it is possible to talk about isometries of a three-dimensional figure. These are distance preserving functions from the figure to itself. The function that reflects the cube in Figure 6.1.3 through a plane halfway between the bottom face and top face exchanges the vertices 1 and 5, 2 and 6, 3 and 7, and 4 and 8 of the cube. This function preserves distances between points in the cube. However, it cannot be achieved by a rigid motion of the cube because a rigid motion that takes vertex 1 to vertex 5, vertex 2 to vertex 6, vertex 3 to vertex 7, and vertex 4 to vertex 8 would not return the cube to its original location; rather it would put the bottom of the cube where its top previously was and would put the rest of the cube above that square rather than below it.
How many elements are there in the group of permutations of \([8]\) that correspond to isometries of the cube?
In how many ways can you choose a place to which you can move vertex 1? Having done that, in how many ways can you place the three vertices adjacent to vertex 1?
Is every permutation of \([8]\) that corresponds to an isometry either a rotation or a reflection?
Why is it sufficient to focus on permutations that take vertex 1 to itself?
We can always figure out the composition of two permutations of the same set by using the definition of composition, but if we are going to work with a given permutation group again and again, it is worth making the computations once and recording them in a table. For example the group of rotations of the square may be represented as in Table 6.1.4. We list the elements of our group, with the identity first, across the top of the table and down the left side of the table, using the same order both times. Then in the row labeled by the group element \(\sigma\) and the column labelled by the group element \(\varphi\text{,}\) we write the composition \(\sigma\circ \varphi\text{,}\) expressed in terms of the elements we have listed on the top and on the left side. Since a group of permutations is closed under composition, the result \(\sigma\circ \varphi\) will always be expressible as one of these elements.
| \(\circ\) | \(\iota\) | \(\rho\) | \(\rho^2\) | \(\rho^3\) |
| \(\iota\) | \(\iota\) | \(\rho\) | \(\rho^2\) | \(\rho^3\) |
| \(\rho\) | \(\rho\) | \(\rho^2\) | \(\rho^3\) | \(\iota\) |
| \(\rho^2\) | \(\rho^2\) | \(\rho^3\) | \(\iota\) | \(\rho\) |
| \(\rho^3\) | \(\rho^3\) | \(\iota\) | \(\rho\) | \(\rho^2\) |
In Table 6.1.4, all the entries in a row (not including the first entry, the one to the left of the line) are different. Will this be true in any group table for a permutation group? Why or why not? Also in Table 6.1.4 all the entries in a column (not including the first entry, the one above the line) are different. Will this be true in any group table for a permutation group? Why or why not?
In Table 6.1.4, every element of the group appears in every row (even if you don't include the first element, the one before the line). Will this be true in any group table for a permutation group? Why or why not? Also in Table 6.1.4 every element of the group appears in every column (even if you don't include the first entry, the one before the line). Will this be true in any group table for a permutation group? Why or why not?
Write down the group table for the dihedral group \(D_4\text{.}\) Use the \(\varphi\) notation described above to denote the flips. (Hints: Part of the table has already been written down. Will you need to think hard to write down the last row? Will you need to think hard to write down the last column? When you multiply a product like \(\varphi_{1|3} \circ \rho\) remember that we defined \(\varphi_{1|3}\) to be the flip that fixes the vertex in position 1 and the vertex in position 3, not the one that fixes the vertex on the square labelled 1 and the vertex on the square labelled 3.)
You may notice that the associative law, the identity property, and the inverse property are three of the most important rules that we use in regrouping parentheses in algebraic expressions when solving equations. There is one property we have not yet mentioned, the commutative law which would say that \(\sigma\circ \varphi = \varphi\circ\sigma\text{.}\) It is easy to see from the group table of \(R_4\) that it satisfies the commutative law.
Does the commutative law hold in all permutation groups?
We have seen that the dihedral group \(D_4\) contains a copy of the group of rotations of the square. When one group \(G\) of permutations of a set \(S\) is a subset of another group \(G'\) of permutations of \(S\text{,}\) we say that \(G\) is a subgroup of \(G'\text{.}\)
Find all subgroups of the group \(D_4\text{.}\)
If a subgroup contains, say, \(\rho^3\) and some flip, how many elements of \(D_4\) must it contain?
Can you find subgroups of the symmetric group \(S_4\) with two elements? Three elements? Four elements? Six elements? (For each positive answer, describe a subgroup. For each negative answer, explain why not.)
There is an even more efficient way to write down permutations. Notice that the product in Figure 6.1.2 is \(\begin{pmatrix}1\amp 2\amp 3\amp 4\cr2\amp 3\amp 1\amp 4 \end{pmatrix}\text{.}\) We have drawn the directed graph of this permutation in Figure 6.1.5.
You see that the graph has two directed cycles, the rather trivial one with vertex 4 pointing to itself, and the nontrivial one with vertex 1 pointing to vertex 2 pointing to vertex 3 which points back to vertex 1. A permutation is called a cycle if its digraph consists of exactly one cycle. Thus \(\begin{pmatrix}1\amp 2\amp 3\cr2\amp 3\amp 1 \end{pmatrix}\) is a cycle but \(\begin{pmatrix}1\amp 2\amp 3\amp 4\cr2\amp 3\amp 1\amp 4 \end{pmatrix}\) is not a cycle by our definition. We write \((1\ 2\ 3)\) or \((2\ 3\ 1)\) or \((3\ 1\ 2)\) to stand for the cycle \(\sigma =\begin{pmatrix}1\amp 2\amp 3\cr2\amp 3\amp 1 \end{pmatrix}\text{.}\)
We can describe cycles in another way as well. A cycle of the permutation \(\sigma\) is a list \((i\ \sigma(i)\ \sigma^2(i) \ \ldots\ \sigma^n(i))\) that does not have repeated elements while the list \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i))\ \sigma^{n+1}(i))\) does have repeated elements.
If the list \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i))\) does not have repeated elements but the list \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i)\ \sigma^{n+1}(i))\) does have repeated elements, then what is \(\sigma^{n+1}(i)\text{?}\)
If the list \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i))\) does not have repeated elements but the list \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i)\ \sigma^{n+1}(i))\) does have repeated elements, then which element or elements are repeats?
We say \(\sigma^j(i)\) is an element of the cycle \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i))\text{.}\) Notice that the case \(j=0\) means \(i\) is an element of the cycle. Notice also that if \(j\gt n\text{,}\) \(\sigma^j(i) = \sigma^{j-n-1}(i)\text{,}\) so the distinct elements of the cycle are \(i\text{,}\) \(\sigma(i)\text{,}\) \(\sigma^2(i)\text{,}\) through \(\sigma^n(i)\text{.}\) We think of the cycle \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i))\) as representing the permutation \(\sigma\) restricted to the set of elements of the cycle. We say that the cycles \((i\ \sigma(i)\ \sigma^2(i)\ \ldots\ \sigma^n(i))\) and \((j\ \sigma(j)\ \sigma^2(j)\ \ldots\ \sigma^n(j))\) are equivalent if there is an integer \(k\) such that \(j= \sigma^k(i)\text{.}\)
Find the cycles of the permutations \(\rho\text{,}\) \(\varphi_{1|3}\) and \(\varphi_{12|34}\) in the group \(D_4\text{.}\)
Find the cycles of the permutation
If two cycles of \(\sigma\) have an element in common, what can we say about them?
Problem 275 leads almost immediately to the following theorem.
for each permutation \(\sigma\) of a set \(S\text{,}\) there is a unique partition of \(S\) each of whose blocks is the set of elements of a cycle of \(\sigma\text{.}\)
More informally, we may say that every permutation partitions its domain into disjoint cycles. We call the set of cycles of a permutation the cycle decomposition of the permutation. Since the cycles of a permutation \(\sigma\) tell us \(\sigma(x)\) for every \(x\) in the domain of \(\sigma\text{,}\) the cycle decomposition of a permutation completely determines the permutation. Using our informal language, we can express this idea in the following corollary to Theorem 6.1.6.
Every partition of a set \(S\) into cycles determins a unique permutation of \(S\text{.}\)
Prove Theorem 6.1.6.
In Problems 273 and Problem 274 you found the cycle decomposition of typical elements of the group \(D_4\) and of the permutation
The group of all rotations of the square is simply the set of the four powers of the cycle \(\rho = (1\ 2\ 3\ 4)\text{.}\) for this reason it is called a cyclic group 3 The phrace cyclic group applies in a more general (but similar) situation. Namely the set of all powers of any member of a group is called a cyclic group. and is often denoted by \(C_4\text{.}\) Similarly, the rotation group of an \(n\)-gon is usually denoted \(C_n\text{.}\)
Write a recurrence for the number \(c(k,n)\) for the number of permutations of \([k]\) that have exactly \(n\) cycles, including 1-cycles. Use it to write a table of \(c(k,n)\) for \(k\) between 1 and 7 inclusive. Can you find a relationship between \(c(k,n)\) and any of the other families of special numbers such as binomial coefficients, Stirling numbers, Lah numbers, etc. we have studied? If you find such a relationship, prove you are right.
The element \(k\) is either in a cycle by itself or it isn't.
(Relevant to Appendix C.) A permutation \(\sigma\) is called an involution if \(\sigma^2=\iota\text{.}\) When you write an involution as a product of disjoint cycles, what is special about the cycles?
