Permutation

A permutation refers to a selection of objects from a set of objects in which order matters. A phone number is an example of a ten number permutation; it is drawn from the set of the integers 0-9, and the order in which they are arranged in matters. Another example of a permutation we encounter in our everyday lives is a passcode or password. To unlock a phone using a passcode, it is necessary to enter the exact combination of letters, numbers, symbols, etc., in an exact order. In cases where the order doesn't matter, we call it a combination instead.

Permutations can be denoted in a number of ways: _nP_r, ⁿP_r, P(n, r), and more.

Permutation formulas

Like combinations, there are two types of permutations: permutations with repetition, and permutations without repetition.

Permutations with repetition

When a permutation can repeat, we just need to raise n to the power of however many objects from n we are choosing, so

n^r

where n is the number of distinct objects in a set, and r is the number of objects chosen from set n. For example, given the set of numbers, 1, 2, and 3, how many ways can we choose two numbers? P(n, r) = P(3, 2) = 3² = 9. We can confirm this by listing all the possibilities:

11		12		13
21		22		23
31		32		33

Permutations without repetition

For permutations without repetition, we need to reduce the number of objects that we can choose from the set each time. For example, given that we have 5 different colored marbles (blue, green, red, yellow, and purple), if we choose 2 marbles at a time, once we pick the blue marble, the next marble cannot be blue. If we were selecting all 5 marbles, we would choose from 5 the first time, 4, the next, 3 after that, and so on, or:

n!

where n is the number of objects in the set, in this case 5 marbles.

5! = 5 × 4 × 3 × 2 × 1 = 120

Refer to the factorials page for a refresher on factorials if necessary. The above means that there are 120 ways that we could select the 5 marbles where order matters and where repetition is not allowed. If we only wanted to select 2 marbles, we need to remove the remaining possibilities by dividing the total number of possibilities by the number of possibilities we don't have to consider, which gives us the formula for permutations without repetition:

P(n, r) =

So for the above example with marbles, if we wanted to choose only 2 marbles, to find how many different ways we can do this, we plug 5 in for n and 2 in for r:

This means that there are 20 ways that we can choose 2 marbles from a set of 5 different marbles.

Using permutations in probability

Permutations can be used to compute complex probability problems. For example, we can use permutations to determine the probability that a 6 digit personal identification number (PIN) has no repeated digits. Assuming that the PIN uses only numbers, there are 10 possible numbers, 0-9, so n = 10. To determine the probability that there are no repeated digits, we need to divide the number of possible 6 digit PINs that don't repeat by the total number of possible PINs with 6 digits. We can find the total number using permutations with repetition, as:

P(n, r) = P(10, 6) = 10⁶ = 1,000,000

The number of 6 digit PINs that don't repeat can be calculated using the formula for permutations with no repetition as:

From this, we can calculate the probability of a 6 digit PIN having no repeating digits as:

There is approximately a 15% chance that a 6 digit pin does not have any repeating digits. There are many other ways that permutations can be used in probability. This is just one example.