Permutations in probability theory and other branches of mathematics refer to sequences of outcomes where the order matters. For example, 9-6-8-4 is a permutation of a four-digit PIN because the order of numbers is crucial. When calculating probabilities, it’s frequently necessary to calculate the number of possible permutations to determine an event’s probability.
In this post, I explain permutations and show how to calculate the number of permutations both with repetition and without repetition. Finally, we’ll work through a step-by-step example problem that uses permutations to calculate a probability.
Definition of Permutations compared to Combinations
Permutations and combinations might sound like synonyms. However, in probability theory, they have distinct definitions.
- Combinations: The order of outcomes does not matter.
- Permutations: The order of outcomes does matter.
For example, on a pizza, you might have a combination of three toppings: pepperoni, ham, and mushroom. The order doesn’t matter. For example, using letters for the toppings, you can have PHM, PMH, HPM, and so on. It doesn’t matter for the person who eats the pizza because you have the same combination of three toppings. In other words, the order of these three letters does not matter and they form one combination.
However, imagine we’re using those letters for a weak password. In this case, the order is crucial, making them permutations. PHM, PMH, HPM, etc., are distinct permutations. If the password is PHM, entering HPM will not work. When you have at least two permutations, the number of permutations is greater than the number of combinations.
In this post, I’m working with only permutations. To learn about combinations, read my post Using Combinations to Calculate Probabilities.
Permutations with Repetition
When the outcomes in a permutation can repeat, statisticians refer to it as permutations with repetition. For example, in a four-digit PIN, you can repeat values, such as 1-1-1-1. Analysts also call this permutations with replacement.
To calculate the number of permutations, take the number of possibilities for each event and then multiply that number by itself X times, where X equals the number of events in the sequence. For example, with four-digit PINs, each digit can range from 0 to 9, giving us 10 possibilities for each digit. We have four digits. Consequently, the number of permutations with repetition for these PINs = 10 * 10 * 10 * 10 = 10,000.
We write this mathematically as nr.
- n = the number of possible outcomes for each event. For instance, n = 10 for the PIN example.
- r = the size of each permutation. For example, r = 4 for a four-digit pin.
Imagine that a class with 15 children can choose one cookie from five types of cookies: Gingerbread, Sugar, Chocolate Chip, Mint, and Peanut Butter. There are enough cookies that they are free to choose one of any type. How many possible permutations of cookies are there?
In this example,
- n = 5 because there are five possible cookie choices.
- r = 15 because there are 15 students in the class, making it the size of the permutation.
Consequently, the are 515 = 30,517,578,125 permutations with repetition. That’s over 30 billion permutations!
If you were to make random guesses for the cookie choice of all 15 children, you’d have a probability of 1/30,517,578,125 of correctly guessing the selections for the entire class! That assumes you don’t have insider knowledge about each child’s cookie preference! I think you’d have better luck in a lottery!
Related post: Fundamentals of Probability
Permutations without Repetition
When the outcomes cannot repeat, statisticians call them permutations without repetition. This situation frequently occurs when you’re working with unique physical objects that can occur only once in a permutation. Imagine you have 10 different books and want to calculate how many possible ways you can arrange them on a bookshelf. After you place the first book, the second book must be a different book. Consequently, this is an example of permutations without repetition. Analysts also call this permutations without replacement.
For the first book, you have 10 books from which to choose. For the second book, you have nine. There are eight options for the third book, and so on. Like before, this process involves multiplying the number of possible outcomes together. However, we must reduce the number of outcomes for each subsequent event.
Mathematically, we’d calculate the permutations for the book example using the following method:
10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3,628,800
There are 3,628,800 permutations for ordering 10 books on a shelf without repeating books.
Whew! I bet you didn’t realize there we so many possibilities with 10 books. I’ll stick to alphabetical order!
Using Factorials for Permutations
When you multiply all numbers from 1 to n, it’s a factorial. In the book example, we multiplied all numbers from 1 to 10. Instead of using the long string of multiplication, you can write it as 10! and read it as 10 factorial.
In general, n! equals the product of all numbers up to n. For example, 3! = 3 * 2 * 1 = 6. The exception is 0! = 1, which simplifies equations.
Factorials are crucial concepts for permutations without replication. The number of permutations for n unique objects is n!. This number snowballs as the number of items increases, as the table below shows.
Partial Permutations without Repetition
In some cases, you want to consider only a portion of the possible permutations. In the bookshelf example, we wanted to know the total number for 10 books. But what if we could fit only five of the 10 books on the shelf? How many permutations of five books are possible using our 10 books?
Use the following formula to calculate the number of arrangements of r items from n objects. There are several standard methods that statisticians use to notate permutations without repetition, which I show below with the formula.
- n = the number of unique items. For instance, n = 10 for the book example because there are 10 books.
- r = the size of the permutation. For example, r = 5 for the five books we want to place on the shelf.
This equation works both for the complete and partial sets of permutations without repetitions, depending on the values you enter in the equation. For complete sets, n = r. Additionally, r cannot be greater than n because there are no repetitions.
For the book example, we have 10 books, but we can put only five on the shelf. The first book still has 10 options. However, for placing the second book, we have only nine options because we already placed one. We have eight options for the third book and so on until we place the fifth book. Mathematically, we’d write this as the following for the five books:
10 * 9 * 8 * 7 * 6 = 30,240
There are 30,240 permutations for placing five books out of our 10 books on a shelf.
Using the equation to calculate the number of permutations
Now, we’ll use the formula to calculate this example. Again, we’ll use n=10 and r=5.
Notice how the 5! cancels itself out in the fraction? That leaves us with the 10 * 9 * 8 * 7 * 6 that we had before.
Here’s how the equation works. The numerator calculates the complete number of permutations for all the unique items. The denominator cancels out the permutations in which we’re not interested. For the book example, the denominator cancels out permutations with more than five books.
Using one form of the notation, we’d write this problem as P (10, 5) = 30,240.
Worked Example of Using Permutations to Calculate Probabilities
When you’re given a probability problem that uses permutations, you need to follow these steps to solve the problem.
- Set up a ratio to determine the probability.
- Determine whether the numerator and denominator require combinations, permutations, or a mix? For this post, we’ll stick with permutations.
- Are these permutations with repetitions, without, or a mix?
- Both types of repetition require you to identify the n and r to enter into the equations.
Problem: What is the probability that a four-digit PIN does not have repeated digits?
This question builds on several of the examples in this post.
Let’s set up our ratio for the probability. In this example, we can use the following ratio for the events of interests and the total number of events.
Let’s tackle the numerator. We need to find the number of four-digit PINs that do not have repeating digits. That’s a permutation because order matters, and it’s without replication because we can’t have repeats. Let’s identify the n and r. We’ll use n=10 because 10 digits are available for the first item and r=4 because we’re discussing four-digit PINs.
Let’s enter that into the equation for permutations without repetition to calculate the numerator:
For the denominator, we need to calculate all possible permutations for four-digit PINs with repeats. We need to enter our n and r into the equation for permutations with repeats.
nr = 104 = 10,000
Consequently, the probability of a four-digit PIN with no repeating digits equals the following:
Just over half of all four-digit PINs have repeated values.
The birthday problem is a classic probability problem. What’s the smallest size group that has a greater than 50% chance of people sharing a birthday? Solving this problem uses similar methods. Read my post about Solving the Birthday Problem to find out!