<< Chapter < Page | Chapter >> Page > |
The concept of a combination did not consider the order of the elements of the subset to be important. A permutation is a combination with the order of a selection from a group being important. For example, for the set $\{1,2,3,4,5,6\}$ , the combination $\{1,2,3\}$ would be identical to the combination $\{3,2,1\}$ , but these two combinations are different permutations, because the elements in the set are ordered differently.
More formally, a permutation is an ordered list without repetitions, perhaps missing some elements.
This means that $\{1,2,2,3,4,5,6\}$ and $\{1,2,4,5,5,6\}$ are not permutations of the set $\{1,2,3,4,5,6\}$ .
Now suppose you have these objects:
1, 2, 3
Here is a list of all permutations of all three objects:
1 2 3; $\phantom{\rule{0.277778em}{0ex}}$ 1 3 2; $\phantom{\rule{0.277778em}{0ex}}$ 2 1 3; $\phantom{\rule{0.277778em}{0ex}}$ 2 3 1; $\phantom{\rule{0.277778em}{0ex}}$ 3 1 2; $\phantom{\rule{0.277778em}{0ex}}$ 3 2 1. $\phantom{\rule{0.277778em}{0ex}}$
Let $S$ be a set with $n$ objects. Permutations of $r$ objects from this set $S$ refer to sequences of $r$ different elements of $S$ (where two sequences are considered different if they contain the same elements but in a different order). Formulas for the number of permutations and combinations are readily available and important throughout combinatorics.
It is easy to count the number of permutations of size $r$ when chosen from a set of size $n$ (with $r\le n$ ).
For example, if we have a total of 5 elements, the integers $\{1,2,3,4,5\}$ , how many ways are there for a permutation of three elements to be selected from this set? In this case, $n=5$ and $r=3$ . Then, $P(5,3)=5!/7!=60!$ .
Show that a collection of $n$ objects has $n!$ permutations.
Proof: Constructing an ordered sequence of $n$ objects is equivalent to choosing the position occupied by the first object, then choosing the position of the second object, and so on, until we have chosen the position of each of our $n$ objects.
There are n ways to choose a position for the first object. Once its position is fixed, we can choose from $(n-1)$ possible positions for the second object. With the first two placed, there are $(n-2)$ remaining possible positions for the third object; and so on. There are only two positions to choose from for the penultimate object, and the $nth$ object will occupy the last remaining position.
Therefore, according to the fundamental counting principle, there are
ways of constructing an ordered sequence of $n$ objects.
Notification Switch
Would you like to follow the 'Siyavula textbooks: grade 12 maths' conversation and receive update notifications?