Permutations

A function is a tuple consisting of a Domain set, D, a Range set, R and a rule \(f\) that for every element \(x\) in \(D\) assigns a unique image element \(f(x).\)
Then the collection of all possible such tuples is a new set \(N.\) Note, by convention, in most cases the tuple \((D, R, f)\) is reduced to simply \(f\) or even \(f:D \rightarrow R.\) While this makes referring to the function much easier, it is crucial to always be aware of the Domain set and Range set that the rule is associated with. There is also an important difference between \(f\) the function and \(f(x)\) that is an element of the Range set.

We say that a function \(f\) is a permutation when:

1. The Domain set \(D\) and Range set \(R\) of a function are equal as sets

2. For every \(y\) in \(R,\) there is a unique element \(x\) with \(f(x)= y.\)

3. For any two elements in \(D,\) say \(x_1\) and \(x_2,\) \(f(x_1) = f(x_2)\) if and only if \(x_1 = x_2.\)

Example 1 Take as the Domain set \(D = \{0, 1, 2, 3, 4, 5 \}\) and the Range set \(R = D = \{0, 1, 2, 3, 4, 5\}.\) The identity function \(id\) defined from \(D\) to \(R\) with the rule \(id(x) = x\) for all \(x\) in \(D\) is a permutation.

There are a few different ways to represent permutations. If the rules associated with the function allow for an enumeration of the outcomes based on non-overlapping subsets of the Domain set, then we can express the rule \(f\) with the following notation where \(S_1, \ldots S_n\) have no elements in common: \(f(x) = \begin{cases} \text{expression 1} & x \in S_1\\ \text{expression 2} & x \in S_2\\ \vdots\\ \text{expression 1} & x \in S_n\\ \end{cases}\)

Example 2 Let the Domain set \(D = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 \}.\) We can partition this set into disjoint sets in many ways, but let us use the collection of sets \(S_1 = {1,2,3,4,5},\) \(S_2 = \{6, 12\}\) and \(S_3 = \{7, 8, 9, 10, 11\}.\) A permutation on \(D\) would be \(f(x) = \begin{cases} 12 - x & x \in S_1\\ x & x \in S_2\\ x - 6 & x \in S_3\\ \end{cases}\) The permutation takes 3 to 9 and 11 to 1. It is also the case that \(f(10) = 4,\) \(f(2) = 10.\)

A permutation can be decomposed into cycles, where an n-cycle is written \((x_1\ x_2 \ldots x_n)\) and implies \(f(x_1)= x_2,\) \(f(x_2) = x_3\) and \(f(x_n) = x_1.\) For the function \(f\) in Example 2, the decomposition of \(f\) is \((1\ 11\ 5\ 7 ) (2\ 10\ 4\ 8) (3\ 9) (6) (12).\) In this representation, \(f\) is a collection of two 4-cycles, a 2-cycle and two 1-cycles. For the function \(id\) in Example 1, the decomposition into cycles is \((1)(2)(3)(4)(5).\)

The collection of all permutations of the elements in \(D\) is a subset of all functions with Domain \(D.\) If the Domain set of \(f\) is finite with size \(\vert D \vert = n,\) then the set of all permutations on \(D\) with composition as the operation defined on the elements is called the Symmetric group of \(D,\) denoted \(Symm(D).\) The pairing of the set of permutations of \(D\) with composition of functions, \(\circ,\) forms a closed set under composition and is a group.
There exists a bijective and homomorphic mapping from the group \((Symm(D), \circ)\) to the permutation group of degree \(n,\) \((S_n, \circ).\)

Example 3 Let \(D = \{0, 1, 2, 3, 4, 5\}\) and define the rule \(r_{1}\)

With cycle notation, \(r_1\) is \((0\ 1\ 2\ 3\ 4\ 5)\) since \(r_1(0) = 1,\) \(r_1(1) = 2,\) \(\ldots,\) and \(r_1(5) = 0.\) To show that \(r_1\) is a permutation, since the Domain set of \(r_1\) is the same collection of elements as the Range set, it is only necessary to show that \(r_1\) is injective and that \(r_1\) is surjective.

What is the size of the set of all possible permutations \(N_{D}?\) From the above illustration, this set contains at least one permutation the identity function so that the image of an element \(x\) in \(D\) is \(x.\) Thus \(N_D\) has size is at least \(\vert N_{D} \vert \geq 1.\) A third presentation for a function defined on a finite Domain set to itself helps us to visualize the answer to this question.

The notation below conveys the rule \(r\) of a permutation on the elements of the set \(D\) that takes \(x_i\) to \(x_{i + 1}\) for \(1 \leq i \leq n-1\) and \(x_1\) is the image of \(x_n\) under \(r.\)

Now, to calculate the number of elements in \(Symm(D),\) where \(\vert D \vert = n,\) notice that there are \(n\) choices for the image of \(x_1.\)

Then, of the permutations with the given choice of image for \(x_1,\) there are now \(n-1\) choices for the image of \(x_2.\) This follows since a permutation must be a surjection.

Continuing to build the permutation in this way we see that the size of the collection of all possible permutation of a set \(D\) with finite size \(\vert D \vert = n\) is the product of 1 through n, which is \(n!\)

Back to course home