# 3.4: Permutations

- Page ID
- 685

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

A *permutation* of \(n\) distinct objects is just a listing of the objects in some order. For example, \([c,b,a]\) is a permutation of the set \(\{a,b,c\}\) of three objects. Likewise, [triangle, melon, airplane] is a permutation of three objects as well. From our mathematical point of view, the objects we use don't actually matter; all we care about is the order they are arranged in. So usually we'll just talk about permutations of the numbers \(1\) through \(n\). You can think of each number as just counting the objects involved: first object, second object, \(n\)th object.

Permutations arise in the world in a many, many ways. For example, suppose you are asked to list your preferences amongst a bunch of presidential candidates. The list you make up, from favorite to least favorite, is a permutation of the candidates. In fact, you can use the mathematics of permutations to learn interesting things about different kinds of voting systems.

Figure 2.3: Instant run-off voting uses a full permutation of the candidates to find a winner. (Source)

Another example is a deck of playing cards. In a standard deck, each card appears exactly once. When you shuffle the deck, you are just creating a random permutation of the cards. One can use mathematics related to permutations to answer interesting questions about cards. Like: 'How many times do I need to shuffle the deck before it is truly randomized?' The answer, by the way, seems to be 7 for a standard riffle shuffle. But proving that is well beyond the scope of these notes!

Because permutations are so common, problems involving permutations tend to be very applicable! For example, suppose you have two hundred students in a class and they all hand in an exam. The stack of exams they give you is a permutation of the students; most likely, the list of student scores you keep is alphabetical. This suggests a problem: What is the fastest way to sort the exams? (In fact, sorting is a fundamental problem in computer science.)

How many permutations are there of a set of \(n\) objects? Suppose we try to build a permutation by successively choosing objects. Then there are \(n\) choices for the first object, \(n-1\) choices for the second, and so on, until there is only one choice for the last object. Then to get the total number of possible permutations, we multiply these numbers together, and get \(n(n-1)(n-2)\cdots 1\). This number, if you haven't seen it before, is called \(n\)-factorial, written \(n!\).

Exercise 2.3.0

Write out all of the permutations of the set \(\{1,2,3,4\}\). How many are there in all? Find a sensible way to organize your list!

Suppose we have some initial ordering of our objects. The letters \(\{a,b,c\}\), for example, can be organized alphabetically. Then every permutation we can think of as a mixing-up of this initial order. In this sense, the permutation is a special kind of function from the set of objects back to itself. (By special, I mean it's a *bijection*, which is to say a one-to-one and onto function.) (TODO: Wikipedia link) A permutation of these objects is then the list \([\sigma(a), \sigma(b), \sigma(c)]\); this list is called the *one-line notation* for \(\sigma\).

These permutations-as-functions can be composed: if you think of two permutations \(\sigma\) and \(\tau\) as different ways to mix up the set, you can mix them up according to \(\sigma\) and then according to \(\tau\). Then the composition is specified by the list \([\tau(\sigma(a)), \tau(\sigma(b)), \tau(\sigma(c))]\).

For example, if \(\sigma=[2,3,1,4]\) and \(\tau=[3,4,1,2]\), then \(\tau\circ\sigma=[4,3,1,2]\). (In particular, \(\sigma(1)=2\), and \(\tau(2)=4\), so the first entry of \(\tau\circ\sigma\) is \(4\). The other three entries are computed similarly.) On the other hand, \(\sigma\circ\tau=[3,1,4,2]\). This is different from \(\tau\circ\sigma\)! So we see that the group of permutations has elements where \(f\circ g\neq g\circ f\); we say that \(S_n\) is *non-commutative*. (But remember that nothing in our group definition says that a group needs to be commutative, so this is ok.)

A very nice way to keep track of this mixing-up is the braid notation for a permutation. This simply writes the list of objects in two lines, and draws a line connecting an object on the top to the object it is sent to under the permutation.

Braid diagrams for some permutations. At this point, we can ask whether the permutations with the composition operation are in fact a group. In fact, they are! Let's check. Let \(\sigma, \tau\) be permutations of the set \(X=\{1,2,3,\ldots , n\}\) Then we can specify \(\sigma\) by the list \([\sigma(1), \sigma(2), \ldots, \sigma(n)]\).

Composition of two permutations is again a permutation. Since each permutation contains every element of \(X\) exactly once, the composition \(\tau\circ\sigma\) must also contain each element of \(X\) exactly once. Identity: The permutation \([1,2,\ldots,n]\) acts as the identity. Inverses: Roughly speaking, if you can mix things up, you can just as easily sort them back out. The 'sorting permutation' of \(\sigma\) is exactly \(\sigma^{-1}\). Associativity: Suppose we compose three permutations, \(\sigma\), \(\tau\), and \(\rho\). Int he braid notation, this just means placing the three braids on top of each other top-to-bottom, and then 'forgetting' the two sets of intermediate dots. (TODO: a picture!) Associativity is tantamount to forgetting the two sets of dots in two different orders; the resulting picture is the same either way, so composition of permutations is associative!

Exercise 2.3.1

Carefully work through the above and check for yourself that permutations satisfy the definition of a group. For example, where it is stated that the identity permutation has one-line notation \([1,2,\ldots,n]\), you should check that this is actually the identity. Likewise, how can you explicitly compute the inverse of a permutation explicitly?

## Contributors

- Tom Denton (Fields Institute/York University in Toronto)