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!

 


Addition and Multiplication Probability Formulas
October 28th, 2016

Rolling dice

Two important probability equations are the multiplication and addition formulas.

The first probability equation is the multiplication formula. This is used to calculate the probability of two events occurring together. The equation is usually written as P(A and B). The formula: P(A and B) = P(A) x P(B). Simple. So the probability of flipping heads and rolling a 4 is 1/2 x 1/6 = 1/12.

The addition formula is used when the question asks about the probability of event A or event B occurring. It’s usually denoted as P(A or B). The probability formula looks like this: P(A or B) = P(A) + P(B) – P(A and B). The probability of flipping heads or rolling a 4 is 1/2 + 1/6 – (1/2 x 1/6) = 7/12.

Basically you add the probability of the two events and then subtract the chance of them both occurring. Picture a venn diagram in which you want to find the total area. To do so, you can find the area of both circles and add them together. But this would double-count the overlapping section of the venn diagram so you need to subtract the area of the overlapping section (in this case, P(A and B)).

There you have it! The two most common probability formulas and equations, the multiplication and addition rules.


New animated video showing how to calculate standard deviation
September 23rd, 2016

I recently finished another animated video, this time explaining how to calculate standard deviation. I hope it’s a useful resource for students and teachers alike. What are your favorite math education videos?


Can you open the secret passageway in time?
September 15th, 2016

rome_passetto_night_inside

You’re in an upstairs hallway of Trump mansion looking at what must be 101 books. You’re not supposed to be here. The party’s downstairs, why did you even come up here in the first place? Oh yeah, you overheard someone mention a secret passageway triggered by pulling two books at the same time on the mahogany bookshelf. You estimate that you can test two book pairs each second. On average, how long will it take you to get through the passageway and achieve unknowable glory?

Show/Hide Solution
Share on FacebookTweet about this on TwitterShare on Google+Email this to someonePin on PinterestShare on StumbleUponShare on Reddit


Pairs of Socks in the Dark
March 19th, 2016

socks!

Remember Jenny? In a rush in the middle of the night, Jenny must grab some pairs of socks out of her drawer for an impromptu vacation, but it’s dark and she can’t see the colors. She knows she has 10 pairs of socks in her drawer: 5 pairs of white socks, 3 pairs of black socks, and 2 pairs of red socks. In an attempt to grab one of each pair, Jenny figures she’ll just grab 5 pairs and hope for the best. What’s the chance that Jenny will end up with at least one pair of each color?

Show/Hide Solution
Share on FacebookTweet about this on TwitterShare on Google+Email this to someonePin on PinterestShare on StumbleUponShare on Reddit


Just released iPhone game called Flippin’ Heads
February 11th, 2016

flippy-coin-app-icon-180

I’ve been working on the game for a few months. Check it out here. Hope you like it!


Law of Large Numbers – Explained and Visualized
December 23rd, 2015

Just finished an animated video explaining the law of large numbers from the field of probability. Check it out:


Blowin’ in the wind
November 14th, 2015

Field of Corn

My brother recently wrote a blog post about GMOs on his science blog and it got me thinking about patented seeds blowing from one field to another.

Imagine you farm a 100×100 yard square field with another 100×100 yard square field directly to your east. The field to your east has patented seeds and you’re worried about the seeds getting blown into your field. The wind is blowing from the northeast and carries a seed about 50 yards. If 9 seeds are released randomly from plants in your neighbor’s field today, what’s the probability that at least one of the seeds blows into your field?

Show/Hide Solution

 


True Story: Travel Coincidence!
October 26th, 2015

Airplane Seats

It’s been a while since the last post. Here’s a situation that actually happened last weekend. My wife and I were flying home from a wedding and the first leg of our itinerary was by chance the same as the first leg of the itinerary of my wife’s sister, who lives in a different state. So, we were going to be on the same plane.

When we got on the plane, which had 12 rows with two seats on either side of the aisle, my wife’s sister was across the aisle from us in the same row! This whole circumstance occurred completely by chance. Since a lot of information needs to be collected to calculate the probability that we were on the same flight, we’ll take that as a given. Given that we were on the same flight, what is the probability that we were sitting next to each other on the flight? Assume that my wife and I will book two seats on the same side of the aisle and my wife’s sister will book an aisle seat.

Show/Hide Solution
Share on FacebookTweet about this on TwitterShare on Google+Email this to someonePin on PinterestShare on StumbleUponShare on Reddit


Flippin’ and Standin’
April 4th, 2015

festive_dinner_table v3

Six people are sitting around a circular table, each holding a fair coin. All six people flip their coins and those who flip heads stand, while those who flip tails remain seated. What is the probability that no two adjacent people will stand?

Show/Hide Solution
Share on FacebookTweet about this on TwitterShare on Google+Email this to someonePin on PinterestShare on StumbleUponShare on Reddit

 


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

Play  |  Explanation  |  Blog  |  History  |  About

© 2016 . All rights reserved.