10.2 Permutations and applications

Permutations

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; $$ 1 3 2; $$ 2 1 3; $$ 2 3 1; $$ 3 1 2; $$ 3 2 1. $$

Counting permutations

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$ ).

1. Select the first member of the permutation out of $n$ choices, because there are $n$ distinct elements in the set.
2. Next, since one of the $n$ elements has already been used, the second member of the permutation has $(n-1)$ elements to choose from the remaining set.
3. The third member of the permutation can be filled in $(n-2)$ ways since 2 have been used already.
4. This pattern continues until there are $r$ members on the permutation. This means that the last member can be filled in $(n-(r-1\left)\right)=(n-r+1)$ ways.
5. Summarizing, we find that there is a total of
   $$n(n-1)(n-2)...(n-r+1)$$
   different permutations of $r$ objects, taken from a pool of $n$ objects. This number is denoted by $P(n,r)$ and can be written in factorial notation as:
   $$P(n,r)=\frac{n!}{(n-r)!}.$$

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!$ .