The Monty
Hall Problem

PLAY GAMEEXPLANATIONBLOG
How to calculate permutations and combinations
November 10th, 2016

 

Just finished creating a new animated video explaining how to calculate permutation and combination problems, helpful for calculating probabilities in many areas. Let me know if you have suggestions for future topics!

Here’s the video transcript:

How much more secure is a 6-digit passcode than a 4-digit passcode?

How many different two-card hands could you get in Texas Hold ‘em?

How many different outcomes are there for the 100m final?

All of these questions can be answered using permutations and combinations, which are part of the field of mathematics awesomely called combinatorics and less awesome called counting.

When working with permutations and combinations, we need to ask two questions to begin solving the problem: “Does order matter?” and “Is repetition possible?”

Whether or not an arrangement of items is called a permutation or combination depends on whether or not the order matters. So the first question to ask is “Does order matter?” If you rearrange the last four digits of your friend’s cell number would that matter? Yes. So we’re dealing with a permutation because order matters. Is a hand with the 2 of clubs and 7 of diamonds different from a hand with a 7 of diamonds and 2 of clubs? No. So we’re dealing with a combination because the order doesn’t matter…and you should fold.

The second question is whether or not repetition is possible. Is it possible to use the same number twice in a passcode? If so, repetition is allowed. Is it possible to have a poker hand with two fives of spades? If not, repetition is not allowed.

So there are four possible scenarios based on whether or not order matters and whether or not repetition is possible. And each one has its own method for counting the number of possibilities. In this video we’ll explain these three and show how to solve sample problems.

We’ll start with permutations with repetition.

Examples of permutations with repetition include passcodes, phone numbers, and even three-scoop ice cream cones if you care about the scoop order and can get multiple scoops of the same flavor.

Consider a 4-digit passcode. Each number in the code can be chosen from the digits 0 through 9. So there are four positions and each position has ten options because it’s possible to repeat numbers. That gives us ten times ten times ten times ten, or ten thousand different passcodes to choose from. The formula for permutations with repetition is nr in which we have n items we could select and r positions for items. In the passcode example, r equals 4 because we have 4 digits, and n equals 10 because we have 10 numbers to choose from for each digit.

Practice problem: A hexadecimal color code is six characters long and each character can be a letter from A to F or a number from 0 to 9. How many hexadecimal color codes are possible? Pause the video and figure it out!

Answer: First we need to determine if we’re dealing with permutations or combinations. Does the order of the characters matter? Is the color BBB333 different from 333BBB? Yes. So order matters. How about repetition? Well we just showed that you can repeat a character. So repetition is possible. We’re solving a problem involving a permutation with repetition. There are 16 possible characters (six letters and 10 numbers) and we’re choosing 6 so there are 166 = 16777216 possible hexadecimal colors!

So that’s permutations with repetition. How about permutations without repetition?

Examples of permutations without repetition include rankings and arranging books on a bookshelf.  

Consider the ways that 8 runners could finish the 100m final. We have eight places and we’ll fill them one by one. There are eight people who could place first. After Usain Bolt places first, there are seven runners who could claim second. For the bronze medal, there are six runners who could take that spot. This pattern continues down to the one person who’s guaranteed last place after the other seven spots are chosen. We can multiply 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 to find the number of possible arrangements or permutations of eight runners.

So our answer would be 8!. The factorial operation multiplies a number by every number less than it all the way down to 1. 4! = 24, and 8! = 40,320. That means there are over 40 thousand possible outcomes for an 8-person sprint.

Now let’s ask a different question: how many possible podium arrangements are there? Now we only care about the first three runners. We follow the same pattern of 8 x 7 x 6 which yields 336 possible podium crews.

This hints at the formula for permutations without repetition. Written as follows and read as “Permutation, n choose r”, it calculates the number of permutations when selecting and arranging r objects from a set of n. If we apply the formula for our podium question, we’d get P(8,3), which equals 8 factorial divided by 8 minus 3, or 5, factorial. If we write out the factorial expressions, we can see that they begin to cancel each other out starting at 5. This means that we’re left with just the first three terms of 8 factorial, which makes sense because we’re choosing three runners from a set of 8.

Sample problem: You have 18 books to your name. Unfortunately, you only have room to display 4 of them on the shelf. How many ways can you do this? Pause the video and figure it out!

Answer: Does order matter? Yes, we’ve decided that different orderings of the books will look different on the shelf. Is repetition possible? No. There’s only one copy of each book. So we’re dealing with a permutation without repetition. We have 18 options for the first position on the shelf, then 17, 16, and 15. Using the formula, we need to calculate Permutation 18 choose 4. That gives us 18 factorial divided by 18 minus 4 factorial, or 14, factorial. It simplifies to what we thought it would 18 x 17 x 16 x 15, which equals 73,440 possible arrangements, an overwhelming amount!

Next we’re going to look at combinations without repetition.

Examples of combinations without repetition include groups of people and poker hands.

Consider all possible two-card Texas Hold ‘em hands. For your first card dealt, there are 52 possible cards, for the second card dealt, there are 51 possible cards. So we could multiply 52 by 51 to find the number of possible two-card hands, however, this would count getting an Ace of clubs then an Ace of diamonds as a different hand than getting an Ace of diamonds then an Ace of clubs, but they’re the same pair of cards. So we need to divide our answer by the two ways that our two objects could be ordered, so we don’t double count the same hand. The answer would be 52 x 51 / 2, or 1326 different two-card hands. The formula for Combinations n choose r is the same as the permutation formula with an additional division by r!, the number of ways that r items could be arranged. This division by r! adjusts the formula to only count different groupings of objects, not the way the objects are arranged within each grouping.

Sample problem: How many 4 person teams could be formed from a group of 23 people? Pause the video and figure it out!

Answer: Is a team with Bob, Sally, Greg, and Stacy the same as a team with Greg, Sally, Stacy and Bob? Yes, we’ve confirmed that order doesn’t matter. Is repetition possible? No, we can’t choose the same person twice for the same team. So we have a Combination 23 choose 4, which is 23 factorial divided by 23 minus 4 factorial times 4 factorial. This gives us 8855 possible teams that could be formed from a group of 23 people.

In conclusion, there are two questions to ask when solving permutation and combination problems: “Does order matter?” and “Is repetition possible?” And now that you know how to calculate permutations with and without repetition and combinations without repetition, consider yourself an expert when it comes to counting.

Have topics you’d like to see in future videos? Please post them in the comments below. Thanks for watching!

 


Click here to view archived puzzles...
Click here to view archived puzzles...

Play  |  Explanation  |  Blog  |  History  |  About

© 2016 . All rights reserved.