Permutations

A permutation is an arrangement or ordering of a number of distinct objects. For example, the words ‘top’ and ‘pot’ represent two different permutations (or arrangements) of the same three letters. A permutation is an arrangement in which order is important. The notation for permutations is P(n,r) which is the number of permutations of “n” things if only “r” is selected.

Example: If nine students take a test and all have different scores, the highest score could be achieved by any of the nine students. The second highest score could be achieved by one of the remaining 8 students. The third highest score could be achieved by one of the 7 remaining students.

The number of possible permutations would be: P (9,3) = 9*8*7 = 504 possible arrangements of the top three scores.

The number of permutations of a set of n elements is denoted n! (pronounced n factorial.)

Thus n! is the number of ways to count a set of n elements. As we saw, 2! = 2. Obviously, 1! = 1, 3! = 6. Indeed, there are just six ways to count three elements:

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

All possible arrangements for a collection of things, where the order is important.

Example: You want to visit the homes of three friends Alex (“a”), Betty (“b”) and Chandra (“c”), but haven’t decided in what order. What choices do you have?

Answer: {a,b,c} {a,c,b} {b,a,c} {b,c,a} {c,a,b} {c,b,a}

If the order does not matter, it is a Combination

How many ways are there to count an empty set, the set with 0 elements? (Note that {0} contains one element thus is not empty. The empty set contains no elements at all – {}.) Since there is nothing to count the question is In how many ways can one do nothing? A mathematical answer to this is just one: 0! = 1.

Permutations Involving Repetitions

Let’s say that we are taking a test, which consists of five multiple choice questions. There are four different answers (a through d) to choose from for each question. What is the total number of ways in which we could answer the five questions on the test?

One way of thinking about this problem is as follows: let’s focus on just the first question on the test. How many choices do we have? The answer to this question is four since we can pick any answer from a to d. Then we ask the same question for each successive question, and clearly, there are four ways of answering each of them. Therefore, the total number of ways for filling out the test is the product of:

4 x 4 x 4 x 4 x 4 =  45

Since we have the same number of choices for each question, the same scenario is repeated for each question on the test. We can generalize our calculations and state that if there are n choices and r repetitions, then the number of permutations or arrangements is given by:

nr

Information Source: