Permutations of Elements in Sets
Consider a finite set $A$ with $n$ elements, say $A = \{ x_1, x_2, ..., x_n \}$. For a more applicable example, suppose that our set $A$ represents a set of $n$ students $x_1, x_2, ..., x_n$, and suppose that we want to know how many ways we can arrange a subset $B$ with $k$ elements (students) in a row.
In answering this question, let's first suppose that we want to know how many ways we can arrange all $n$ students in a row of $1$ desk. In other words, we want to find the number of different lists of length $1$ that can be formed from the elements of $A$. It's not too hard to see that there are $n$ of these lists, namely $(1), (2), ..., (n)$.
Now suppose that we want to know how many ways we can arrange all $n$ students in a row of $2$ desks. We thus want to find the number of different lists of length $2$ that can be formed from the elements of $A$. In this case, we have that the first position can be occupied by $n$ different students while the second position can be occupied by $n-1$ different students (one less since the student occupying the first position cannot simultaneously occupy the second position), and so there are $n(n-1) = n^2 - n$ of these lists, namely $(1, 2), (1, 3), ..., (1,n), (2, 1), (2, 3), ..., (2, n), ..., (n, 1), (n,2), ..., (n, n-1)$.
If we continue forward, then we may want to know how many ways we can arrange all $n$ students in a row of $n$ desks, i.e., determine how many different lists of length $n$ we can create from the elements in $A$. In the first position of the length $n$ list we have $n$ students to pick from. After we place that student, then we have $n - 1$ students to pick and place in the second position, and so forth. We therefore see there are $n(n-1)(n-2)...1 = n!$ ways to arrange all $n$ students in a row.
The above examples illustrate a $1$-permutation, $2$-permutation, and $n$-permutation of an $n$-element set of students.
| Definition: A $k$-Permutation is an ordered arrangement of $k$ elements from a finite $n$-element set $A$. |
// The term "permutation" alone means an $n$-permutation, i.e., a permutation of all elements in an $n$-element set.//
For a simple example, consider a set of numbers $A = \{1, 2, 3 \}$. Then an example of a $2$-permutation from elements in $A$ could be the ordered arrangement (list), $(1, 2)$. In fact, $(1, 3)$, $(2, 1)$, $(2, 3)$, $(3, 1)$, $(3, 2)$ are also $2$-permutations of the elements from $A$ and it's not hard to see that these are the only $2$-permutations of $A$.
For a less formal example, consider a set of people containing Mary, Joe, and Fred. Suppose that we wanted to pick $2$ of these people and arrange them in a line of $2$. Like with the previous example, there are $6$ ways to accomplish this. That is (Mary, Joe), (Mary, Fred), (Joe, Mary), (Joe, Fred), (Fred, Mary), and (Fred, Joe). Note that the order is very important since it tells us which of the three individuals is in the front of the row and which of them is in the back of the row.
It is often useful to know the total number of $k$-permutations from an $n$-element set. The following theorem gives us a formula for finding the total number of these $k$-permutations.
| Theorem 1: If $A$ is an $n$-element set then the number of $k$-permutations from $A$ is given by $P(n, k) = n \cdot (n-1) \cdot ... \cdot (n - k + 1) = \frac{n!}{(n - k)!}$. |
If $k > n$ then the definition of a permutation makes no sense, so in such cases we will define $P(n, k) = 0$, i.e., there will be $0$ ways to arrange a larger number of elements than the total number of elements that we can possibly arrange. Furthermore, we will adopt the convention that $0! = 1$.
- Proof: Fix $n$ as a positive integer and let $A = \{ x_1, x_2, ..., x_n \}$. For $0 \leq k \leq n$ consider the possible ordered lists of length $k$. In the first position, we can choose any element in $A$ and there are $n$ of them. Without loss of generality, assume that we choose $x_1$. Now for the second position, we can choose any element in $A \setminus \{ x_1 \} = \{ x_2, x_3, ..., x_n \}$. By the subtraction principle, this set has $n - 1$ elements to choose from. Without loss of generality, assume that we choose $x_2$. We continue onward in this fashion. In the $k^{\mathrm{th}}$ position, we can choose any element in $A \setminus \{ x_1, x_2, ..., x_{k-1} \}$. By the subtraction principle once again, we see that there are $n - (k-1) = n - k + 1$ elements to choose from. Thus the total number of $k$-permutations from $A$ is:
The formula in Theorem 1 above is very important in solving simple counting problems. For example, suppose we want to construct a flag of three colours coming from the colours red, orange, yellow, green, blue, and purple of the rainbow. Let $A$ be the set of these colours, that is:
(2)In this example, the total number of colours to choose from is $n = 6$ and the number of colours we are selecting is $k = 3$. Thus, by Theorem 1 we have that the total number of flags we can construct choosing $3$ colours from the set $A$ is:
(3)