Permutations and Combinations
Learning Objective(s)
· Use the Fundamental Counting Principle to compute permutations and combinations.
Introduction
Some probability situations involve multiple events. When one of the events affects the others, they are called dependent events. For example, when items are chosen from a list or group and are not replaced, the first choice reduces the options available for later choices.
There are two possible ways to arrange or combine outcomes of dependent events. Permutations are groupings in which the order of items matters. Combinations are groupings in which content matters but order does not.
Dependent Events
Two events are dependent if the original state of the situation changes from one event to the other event, and this alters the probability of the second event.
| Dependent events occur when an action removes a possible outcome, and the outcome is not replaced before a second action takes place.
This is referred to as choosing without replacement. |
So one way to tell whether events are dependent or independent is to find out whether a removed outcome is replaced (making them independent) or not replaced (making them dependent). Here are some examples:
| Situation | Events | Why the events are dependent |
| At a party, you draw four names of the guests to form a team of four people. What’s the probability that John, Perna, Tosho, and Lee will be on a team together? | Draw John Draw Perna Draw Tosho Draw Lee | Once you draw a name, you don’t put that name back into the pool of names you draw from. Each time, there is one fewer name in the sample space, and (if the event continues to occur) one fewer name in the event space. The probability that the event happens changes with each new draw. |
| You pull a marble from a bag with 2 red, 2 white, and 1 green marble. You hold onto it and then pull another marble. What's the probability of pulling a red marble and then pulling the green marble? | First pull is red. Second pull is green. | The events are dependent because you don’t replace the first marble you pull. There is one fewer marble in the sample space, so the probability of picking a green one is different for the second pull than it was for the first pull.
|
| You draw two cards from a standard deck of 52 cards. (In a standard deck, each card has a suit—hearts, clubs, diamond, or spades—and a rank—Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, or King. What’s the probability both cards are 2s? | One card is a 2. The other card is a 2. | Since two cards are drawn, the probability that the first is a 2 is different from the probability that the second is a 2. (Fewer cards to choose from gives a smaller sample space.) |
| Beth has 10 pairs of socks: 2 black, 2 brown, 3 white, 1 red, 1 blue, and 1 green. Today she wants a white pair, but she’s in a hurry to get to work, so she grabs a pair randomly, without looking. If it’s not white, she’ll throw it on her bed and try again. Choose the sentence that best matches this situation.
A) The events are dependent, because Beth doesn't remove any outcomes. B) The events are dependent, because the removed outcome is replaced after each try. C) The events are dependent, because an outcome is removed with each try and not replaced.
|
to 
. The events are dependent, because an outcome is removed with each try and not replaced.
One thing we know about situations involving dependent events is that one action removes possible outcomes from future actions. There's another important issue to consider about the outcomes of dependent events: how are they organized? Must we make a list, noting the order in which they occurred, or do we just lump them together and ignore the order?
Consider the three examples given before, and think about whether order matters:
| Situation | Events | Does the order matter? |
| At a party, you draw four names of the guests to form a team of four people. What’s the probability that John, Perna, Tosho, and Lee will be on a team together? | Draw John Draw Perna Draw Tosho Draw Lee | Order doesn’t matter. Those four people will be on the same team whether you draw John, Perna, Tosho, and then Lee, or Perna, Tosho, Lee, and finally John.
|
| You pull a marble from a bag with 2 red, 2 white, and 1 green marble. You hold onto it and then pull another marble. What's the probability of pulling a red marble and then pulling the green marble? | First pull is red. Second pull is green. | Order matters. Pulling a green and then a red is not a successful outcome for this situation.
|
| You draw two cards from a standard deck of 52 cards. (In a standard deck, each card has a suit—hearts, clubs, diamond, or spades—and a rank—Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, or King. What’s the probability both cards are 2s? | One card is a 2. The other card is a 2. | Order does not matter. The outcome is satisfied whether you draw the 2 of hearts and then the 2 of clubs, or the 2 of clubs and then the 2 of hearts. |
In situations that create groups of objects (such as people, marbles, or cards), we need to know whether their order matters or not. Otherwise we can't find the sample and event spaces accurately.
Consider the team example. In the sample space, the outcome John, Perna, Tosho, Lee is the same as the outcome Perna, Lee, John, Tosho—there is no difference between the teams created, even though the members are named in a different order. On the other hand, suppose the first person drawn had to be the one to toss a water balloon, the second had to be the one who caught it, the third had to be the one who pops it (if it’s still intact), and the fourth is the one who tries to catch the water in a cup! If John is a terrible balloon thrower but Perna is great at it, it would be better for the team to be Perna, Lee, John, Tosho (so Perna throws to Lee) than John, Perna, Tosho, Lee (John throws to Perna). Order matters.
| Example | |||||||||||||||||||||||||||||||||||||||||||||||||
| Problem | A bag contains 5 marbles, colored white, red, blue, purple and green. Find the size of the sample space if you pull two marbles, without replacement, in two ways: 1) Order matters. 2) Order does not matter. |
| |||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
| List the possibilities for the first pull. To save space, just use the initials of the colors (since they’re all different). | ||||||||||||||||||||||||||||||||||||||||||||||
|
|
Sample space (order matters): {RW, BW, PW, GW, WR, BR, PR, GR, WB, RB, PB, GB, WP, RP, BP, GP, WG, RG, BG, PG} |
| Now add the second pull. Since we first want to look at when order matters, just add the second pull after the first one. Remember that this is without replacement, so you can’t repeat a color.
| ||||||||||||||||||||||||||||||||||||||||||||||
|
|
Sample space (order doesn’t matter): {RW, BW, PW, GW, BR, PR, GR, PB, GB, GP} |
| Now, how is this different when order doesn’t matter? WR and RW become the same outcome, as do WB and BW, and so on. In the diagram here, each outcome is paired with the equivalent outcome. Since you only need one of each pair, there are half as many outcomes. | ||||||||||||||||||||||||||||||||||||||||||||||
| Answer |
When order matters, the sample space has 20 outcomes. When order doesn’t matter, the sample space has 10 outcomes. |
|
| ||||||||||||||||||||||||||||||||||||||||||||||
When we make groups in which the order doesn’t matter, the groups are called combinations. When we make groups in which the order does matter, the groups are called permutations. Remember, with permutations, position (order) matters.
Sample Size and the Fundamental Counting Principle
Since sample and event size are what we use to find probabilities, it’s helpful to know just how many combinations or permutations are possible. Here’s a way to think about it, using the Fundamental Counting Principal, which says that the number of outcomes in the sample space is the product of the number of outcomes for each element.
Let’s start with permutations, when order matters. Suppose we have n objects to choose from (n marbles in the bag, or n guests at the party, for example).
· The first draw has a choice of n objects
· For each of those n objects, there are n − 1 choices for the second draw. Using the Fundamental Counting Principal, that means there are n • (n − 1) outcomes for choosing two things.
· Now, for each of those n • (n − 1) outcomes, a third choice can be made from the n − 2 objects that remain. Using the Fundamental Counting Principal again, there are n • (n − 1) • (n − 2) possible outcomes for 3 draws.
See where this is going? Notice that the last factor subtracts one less than the total number of objects chosen. To find the number of options for choosing the kth object, multiply the previous outcomes by n − (k − 1). Another way to write n − (k − 1) is n − k + 1.
| Permutations When choosing k of n objects and order matters, the number of permutations is
The symbol “…” means continue in the same way. In this case, it means continue to multiply by the next lower whole number, through n – k + 1. |
For combinations, order doesn’t matter. How does that change the number of outcomes? The number of permutations that become the same when order no longer matters is the number of ways to arrange the objects in a group.
Think about a group of three letters, ABC. In a permutation situation, ABC and CAB are different outcomes, but in a combination situation, these outcomes are the same. How many different ways can the letters A, B, and C be arranged? That is, how many permutations are there for this one particular group?
ABC ACB
BAC BCA
CAB CBA
There are 6 ways to arrange the letters. Notice that what we’re doing is finding the number of permutations of 3 objects when we choose all 3 (n = 3 and k = 3). So, using the formula provided above, there are 3 • 2 • 1 = 6 outcomes. This matches the list of actual outcomes.
In the marble example, we had 2 objects in each group, so for each pair of marbles, there were 2 • 1, or 2, ways to arrange them. We only needed one from each pair, so the number of combinations was the number of permutations divided by 2. In the letter example, since there are 6 ways to arrange three objects, when we’re finding combinations of three we only need one representative from those 6 ways. We can divide the number of permutations by 6 to get the number of combinations.
This is true in general: to find the number of combinations of k objects taken from n objects, divide the number of permutations for choosing k of n objects by the number of permutations for choosing k of k objects.
| Combinations
When choosing k of n objects and order doesn’t matter, the number of combinations is the number of permutations for k of n objects divided by the number of permutations for choosing k of k objects:
|
Sample Size and Factorials
There’s an easier way to write permutation and combination formulas, using an idea called factorials. A factorial is a product of all the whole numbers from 1 to a given number. The symbol ! after a number is used to represent this product. For example, 3! = 3 • 2 • 1, and 7! = 7 • 6 • 5 • 4 • 3 • 2 • 1. So, in general, n! = n • (n − 1) • … • 2 • 1. Special note: 0! is defined to be 1.
The number of permutations formula starts out like n!, but it ends with (n − k + 1) instead of 1. We need to remove the factors from (n − k) to 1 from the product. We can do that by dividing by (n − k)!
Then, for combinations, we divide that result by k • (k − 1) • … • 2 • 1, or k!
| Using Factorials
When choosing k of n objects, the following formulas can be used:
Number of permutations =
Number of combinations =
|
Many calculators have a factorial (!) key or command. To find the number of permutations of choosing 20 of 24 objects, entering 24! ÷ 4! is a lot faster and easier than 24 • 23 • 23 • 21 • 20 • 19 • 18 • 17 • 16 • 15 • 14 • 13 • 12 • 11 • 10 • 9 • 8 • 7 • 6 • 5. (Then again, if only 4 choices are made, it may still be easier to enter 24 • 23 • 22 • 21.)
Let's try these formulas on a problem. First, we'll use the Fundamental Counting Principle.
| Example | ||||||
| Problem | A school organization has 30 members. Four members will be chosen at random for an interview with the school newspaper about the group. How many groups of four are possible? |
| ||||
|
|
combination |
| First, decide if this is a permutation or a combination situation.
There’s no reason for any person to be considered different from any other, based on the order chosen, so this is a combination. | |||
|
|
|
| There are 30 possibilities for the first pick. Then 29 possibilities for the second person, 28 for the third, and 27 for the fourth. The Fundamental Counting Principle says we multiply these outcomes to get the total number of possibilities. | |||
|
|
|
| However, that product gives us the number of permutations, when order matters. We need to take all the arrangements of four particular people and use just one representative of each.
For four people, there are 4 choices for the first to be listed, 3 choices for the second, 2 for the third, and then only 1 choice for the last in the list. The Fundamental Counting Principle again tells us how many times a group of 4 people will show up in the permutations list.
Divide by the product provided by the Fundamental Counting Principle. | |||
| Answer | There are 27,405 different groups of 4 people possible from the 30 members! |
|
| |||
Now we'll solve the same problem with the factorial formula:
| Example | ||||
| Problem | A school organization has 30 members. Four members will be chosen at random for an interview with the school newspaper about the group. How many groups of four are possible? |
| ||
|
|
combination |
| First, decide if this is a permutation or a combination situation.
There’s no reason for any person to be considered different from any other, based on the order chosen, so this is a combination. | |
|
|
|
| The factorial formula for combinations is
In this case, we’re choosing 4 of 30 members, so n = 30 and k = 4. | |
| Answer | There are 27,405 different groups of 4 people possible from the 30 members! |
|
| |
Both methods produced the same answer.
| A group of eight friends are playing a board game in which the players race to the last spot on the board. The friends agree to play for first, second, and third place. How many ways are there for the eight friends to take those places?
A) 6 B) 56 C) 336 D) 40,320
|
Summary
Two (or more) events are dependent if the probability for one event changes when the success of the other event is determined. This typically happens when the random action for one event removes a possible outcome and the outcome is not replaced before the action for the other event happens.
To find the sample and event spaces for these situations, consider whether the events involve permutations (order matters) or combinations (order does not matter.) There are two ways to calculate sample and event space without listing them all and counting, with the Fundamental Counting Principal and with factorial formulas.
The Fundamental Counting Principle allows us to find the number of permutations and combinations as follows:
When choosing k of n objects, the number of permutations is 
When choosing k of n objects, the number of combinations is 
Factorial formulas calculate permutations and combinations this way:
When choosing k of n objects, the number of permutations =
When choosing k of n objects, the number of combinations = 
