Some of the Math of Permutations

Definitions

A permutation is a function from a set into itself that is both 1 - 1 and onto. You probably know what those terms mean already, but just to refresh, a function is said to be one to one (1-1) if whenever \( f(x) = f(y) \), then \( x = y\). Symbolically \( f(x) = f(y) \Rightarrow x = y \). This is often written as \( f: X \xrightarrow{\text{1-1}} Y\). A function from \(X\) to \(Y\) is said to be onto if every \(y\) in the set \( Y \) has at least one \(x\) in the set \(X\) such that \( f(x) = y\), in mathematical notation, \( \forall{y \in Y} \exists x \in X f(x) = y\). This is often written \( f:X \xrightarrow{\text{onto}} Y \). Another name for a function that is both 1-1 and onto is a bijection. They are often written \( f: X \xrightarrow{\text{1-1, onto}} Y\).

Easy enough, right? The fact that you’re here reading about them on this page means that you’ve probably heard about them before and might even know much more about them than I do. I’m not an expert or anything like that. The first thing we’re going to do is show that they form a group under composition, then we’ll do some very basic counting of them, and finally show that they can be split into two disjoint sets. One set is the collection of even permutations, and the rest are the odd permutations. For the rest of this article, we will only be dealing with permutations of a finite set. In particular, let’s assume \( X \) has exactly \( n \) distinct elements. When we say “form a group under composition”, what we mean by “composition” is just taking a function of a function. \( f(g(x)) \). It is also often written as \( f \circ g (x) \). First we apply \( g \) to \(x\), and then we apply \( f \) to \( g(x) \). In order to show that the set of all permutations from a set \( X \) into itself is a group we need to establish four facts

Definition of a Group

To show 1, notice that \( \iota(x) = x \) works. It changes nothing.

To show 2, define \( \tau(x) \) as follows $$ \begin{align} \tau(x) &:= y \\ \\ &\text{where} \\ \\ \sigma(y) &= x \\ \end{align} $$

How do we know this will work? We need to show two things. First we need to show that \( \tau(x) \) is defined for every \( x \), but that’s not a problem because every permutation is a bijection (from a set \( X \) into itself), and therefore every permutation is onto, so we are guaranteed that there is an \( y \), such that \( \sigma(y) = x \). The second thing we need to check is that this function is well-defined. I.e. that we aren’t going to end up with \( \tau(x) = y \) and \( \tau(x) = z \), where \( y \neq z \). In order for that to happen, \( \sigma(y) = x \), and \( \sigma(z) = x \), but since \( \sigma \) is a bijection, it is 1-1, and so \( \sigma(y) = \sigma(z) \Rightarrow y = z \), so \( \tau(x) \) can’t be two different values, and \( \tau \) is well-defined. \( \tau \) is called the inverse of \( \sigma \) and is often written as \( \sigma^{-1} \).

To show that 3 holds, notice that \( \sigma \circ \tau \) is a function from \( X\) into itself (because both \( \sigma \) and \( \tau \) are functions from \( X \) into itself), and that \( \sigma \circ \tau(x) \) is defined to be \( \sigma ( \tau (x )) \). We now have to show that it is a bijection. I.e. that it is 1-1 and onto. Suppose \( \sigma( \tau(x)) = \sigma( \tau(y)) \). Define

$$ \begin{align} u &:= \tau(x) \\ \\ &\text{and} \\ \\ v &:= \tau(y) \\ \end{align} $$

So, \( \sigma( u ) = \sigma (v) \). Since \( \sigma \) is 1-1, we can conclude that \( u = v \). And that means that \( \tau(x) = \tau(y) \), which similarly means that \( x = y \). Thus \( \sigma \circ \tau \) is 1-1. Now let’s show that it’s onto. Let \( z \) be any element of \( X\). We want to find an \( x \) in \( X \) such that \( \sigma \circ \tau(x ) = z \). Since \( \sigma \) is a bijection, it is onto, and so there is a \( y \in X \), such that \( \sigma(y) = z \). Likewise, \( \tau \) is a bijection, so there is an \( x \in X \), such that \( \tau(x) = y \). Thus,

$$ \begin{align} \sigma \circ \tau (x ) &= \sigma ( \tau (x)) \\ &= \sigma(y) \\ &= z \\ \end{align} $$

So \( \sigma \circ \tau \) is onto. Therefore it is a bijection and a permutation of \( X \).

Finally, to show 4 note that

$$ \begin{align} &\sigma \circ (\tau \circ \upsilon)(x) &&= \sigma \circ ( \tau(\upsilon(x)) ) \\ &\sigma \circ ( \tau(\upsilon(x)) ) &&= \sigma ( \tau ( \upsilon (x) ) ) \\ &\sigma ( \tau ( \upsilon (x) ) ) &&= (\sigma \circ \tau) ( \upsilon(x) ) \\ &(\sigma \circ \tau) ( \upsilon(x) ) &&= ( \sigma \circ \tau ) \circ \upsilon (x) \\ \end{align} $$

QED

Now we’re going to count permutations. We’ll show that if \(X \) is a set with \( n \) distinct elements, then the number of permutations of \(X \) is equal to \( n (n-1) (n-2) \cdot … \cdot 2 \cdot 1 \). This is usually written \( n! \). The proof I’m going to give is a bit more involved than most proofs, but I hope that it will still be easy to follow. I’m going to use induction to count the number of 1-1 functions $$ \begin{align} &\text{from } &&X|_k &&{=}&& \{ x_1, x_2, … x_k \} \\ &\text{to } &&X &&{=}&& \{x_1, x_2, … x_{n-1}, x_{x} \} \\ \end{align} $$

Lemma

Proof

By induction on \(k\) ( \(n\) is assumed to be fixed). Let \( k =1 \). Notice that since the domain of \( \sigma|_1 \) has only one element (i.e. \( x_1\)), that it is necessarily 1-1. There are exactly \( n\) distinct \( \sigma|_1 \), each one sends \( x_1 \) to a different element of \( X\).

Now, assume that the lemma holds for \(k \), and we’ll show that it holds for \( k+1 \) (provided \( k + 1 \leq n \) ). In order to do this we have to show that there are exactly \( n - k \) times as many 1-1 functions \( \sigma|_{k+1} \) as there are \( \sigma|_{k} \). By induction we may assume that all \( \sigma|_k \) are unique. Let \( \tau|_k \) be an arbitrarily chosen 1-1 function on \(X|_k\). Notice that \( x_{k+1} \) is not in the domain of \( \tau|_k \), so we can extend it to a \( \tau|_{k+1} \) by defining it on \( x_{k+1} \). What are the possible \( y \in X \), such that we could set \( \tau|_{k+1}(x_{k+1}) = y \) ? Notice that since \( \tau|_{k+1} \) is 1-1, it can’t be any of

$$ \begin{align} &\text{Range}({\tau|_k}) = \\ &\{ \tau|_k(x_1), \tau|_k(x_2), …, \tau|_k(x_k) \} \end{align} $$

Therefore it can be any element left over in \( X \setminus \text{Range}(\tau|_k)\). Notice that \(X \) has exactly \( n \) elements and \( \text{Range}(\tau|_k) \) has exactly \( k\) elements, so \( X \setminus \text{Range}(\tau|_k)\) has exactly \( n - k \) elements for us to choose from. Thus, as we wanted, there are exactly \( n - k \) ways to extend every \( \sigma|_k \) to a \( \sigma|_{k+1} \).

Using this lemma, we see that when \( k = n\), there are \( n!\) distinct 1-1 functions from \(X \) to itself. If we can show that each 1-1 function is also onto, then we’ll have counted bijections from \( X \) to itself, and our proof will be complete. This is quite easy to show, since the size of the range of any \( \sigma|_k \) is \( k \), so when \( k = n \), the size of the range will be exactly the size of \(X\) and \( \text{Range}(\sigma|_n) \subseteq X \), so \( \text{Range}(\sigma|_n) = X \), and our functions are onto.

QED

Next we show that permutations can be separated into two distinct classes, the even permutations and the odd permutations. First notice that when we were dealing with permutations on a set \(X\) above we had to fix an order to the elements of \(X\), i.e. \(X = \{ x_1, x_2, … , x_n\} \). And a permutation, \( \sigma \) re-ordered \(X\) as \( \{ \sigma(x_1), \sigma(x_2), … , \sigma(x_n) \} \). We get the same effect if we consider

$$ \begin{align} \dot{\sigma} : &\{1, 2, … , n\} \xrightarrow{\text{1-1, onto}} \\ &\{1, 2, … , n\} \\ \end{align} $$

where if \( \sigma(x_i) = x_j \), then \( \dot{\sigma}(i) = j \). Then a permutation \( \sigma \) has a sign, defined as:

\[ \text{Sign}(\sigma) := \prod\limits_{i > j}{\frac{\dot{\sigma}(i) - \dot{\sigma}(j)}{i - j}} \]

We’ll prove some interesting properties of \( \text{Sign} \) in the next entry More Math of Permutations.