Calculate probabilities involving multiple applications of the fundamental counting principle, combinations, and/or permutations.
Combinatorics is the name applied to mathematical techniques for counting how many possible arrangements or groupings are possible. For example, we can determine how many different Washington State license plates are possible or how many possible five-card poker hands have three kings.
Subsection5.4.1Tree Diagrams and the Fundamental Counting Principle
Recall from Section 5.1 that the sample space when three coins are flipped is \(\{HHH,HHT,HTH,HTT,THH,THT,TTH,TTT\}.\) There are eight elements. We can depict this sample space using a tree diagram.
In the diagram, we start with a node at the top. (Tree diagrams also can be oriented horizontally, from left to right.) The first coin can result in either heads or tails, which is denoted by the first split or set of branches. Then, regardless of whether the first coin landed heads or tails, the second coin lands either heads or tails. The second flip is indicated using splits or branches from the ends of the first. Then the third flip is indcated by branches from the ends of the second.
Figure5.4.1.Tree diagram for three coin flips
To read the outcomes, we follow each path in the tree diagram. For example the path highlighted below shows heads on the first flip, tails on the second, and heads on the third.
Figure5.4.2.Tree diagram for three coin flips one path highlighted for emphasis.
Each path corresponds to a unique element in the sample space. In the bottom row, there are a total of eight endpoints, which are the ends of the eight paths representing the sample space. Using a tree diagram such as this, we can visualize all the elements in a sample space.
Observe that in each splitting, the number of branches was multiplied by two, representing the two possible outcomes of each coin flip. As illustrated in the tree diagram, there are \(2\cdot 2 \cdot 2 = 8\) possible outcomes when flipping three coins.
Example5.4.3.
Make a tree diagram to depict the all possible sandwiches using one kind of bread, one kind of meat and one kind of cheese. The bread choices are white, whole wheat, and rye, the meat choices are turkey and ham, and the cheese choices are cheddar and jack. Then use the tree diagram to find how many different sandwiches can be made.
Solution.
To find the number of sandwiches that can be made, we can add the number of ending points on the tree diagram to get 12.
Note that after each decision, the number of branches is multiplied by the number of choices for that decision. For example, after choosing the bread, there were three branches, and after choosing the meat, there were two branches for each bread choice resulting in \(3\cdot2=6\) bread and meat combinations. In general, we can multiply the number of choices for each decision to find the total number of possible outcomes. In the example above, there were three choices for bread, two choices for meat, and two choices for cheese. Multiplying the number of choices for each decision gives the total number of possible sandwiches: \(3\cdot2\cdot2=12.\)
This approach of multiplying the number of choices (outcomes) for each decision (event) is known as the Fundamental Counting Principle.
Fundamental Counting Principle.
To find the total number of outcomes of two or more events in succession, multiply the number of possible outcomes for each event given that each previous event occurred.
Example5.4.4.
Suppose three cards are drawn from a standard 52-card deck without replacement.
How many ways can three cards be drawn from the deck?
How many ways can three cards be drawn from the deck if all three cards are hearts?
A Washington State license plate consists of three letters followed by four numbers between zero and nine. What is the probability that a plate consists of three vowels followed by four even numbers? The English vowels are A, E, I, O, and U.
Solution.
There are 26 letters in the English alphabet, and there are 10 digits between zero and nine. Taking each number or digit on the license plate as an event, the total number of license plates possible is
There are five vowels and five even digits. This results in five "choices" for each of the seven spots on the license plate. The resulting total is
\begin{equation*}
5^{7}=78\,125.
\end{equation*}
Therefore, the probability of a randomly-generated license plate consisting of three vowels and four even numbers is \(\frac{78125}{175760000}\approx0.044\%\)
Subsection5.4.2Factorials
Consider the example of how many ways a competition among six teams can end, assuming there are no ties. Any of the six teams can come in first, then one of the five remaining teams can come in second, and so forth. The total number of possible rankings of the six teams is
Because we so frequently multiply whole numbers by each subsequent lesser whole number all the way down to one, we have a name and special notation for this calculation. We call it a factorial and write it \(n!\) with an exclamation point.
Example5.4.6.
Calculate \(4!\) by hand.
Solution.
\(4\cdot 3 \cdot 2 \cdot 1 = 24\)
Example5.4.7.
Calculate \(\frac{52!}{5!\cdot47!}\) on a calculator.
Solution.
The answer is \(2\,598\,960\text{.}\)
Using the factorial function on a scientific calculator, this is entered as:
Seven volumes of a book series are placed randomly on a shelf. What is the probability that they are arranged in the correct order, volume 1 followed by volume 2, and so on?
Solution.
When placing the books on the shelf, there are seven choices for the first book, six remaining choices for the second book, five choices for the third book, et cetera. The total number of arrangements is \(7!\text{.}\) Only one of these arrangements is correct. Therefore, the probability is
Factorials can be used to calculate the number of arrangments of subsets of objects as well. For example, the number of ways that four cards can be dealt from a standard 52-card deck is \(52\cdot51\cdot50\cdot49=6,\!497,\!400\text{.}\) This is the same as \(\frac{52!}{48!}=6,\!497,\!400\) because the \(48!\) in the denominator "divides away" the remaining factors of \(52\cdot51\cdot50\cdot49\cdot48\cdot47\cdots1\) leaving just the first four factors. The resulting calculation is called a permutation, which we discuss next.
Subsection5.4.3Permutations
Suppose we wanted to find the number of ways that 20 cards can be dealt from a standard 52-card deck. It would be tedious to multiply 52 by 51 by 50 and so on all the way down to 33. Instead, we can use factorials to calculate this more efficiently. The number of ways that 20 cards can be dealt from a standard 52-card deck is
which is such a large number that we have expressed in scientific notation.
In this example, we are considering different arrangements of 20 cards. For example, if the first card dealt is the ace of spades and the second card dealt is the two of hearts, this is a different arrangement than if the first card dealt is the two of hearts and the second card dealt is the ace of spades. We will only consider such scenarios right now and address how to handle situations where the order doesn’t matter later in this section.
To generalize, we notice that the factorial in the denominator is the factorial of \(52-20\text{.}\) So the numerator is the factorial of the total number of objects, and the denominator is the factorial of the total number of objects minus the number of objects we are arranging. Thus, tthe number of arrangements of \(r\) objects pulled from a set of \(n\) objects is equal to \(\frac{n!}{(n-r)!},\) and this calculation is called a permutation.
Permutations.
A permutation is the number of arrangements of \(r\) objects selected from a set of \(n\text{.}\)
Permutations are groups of \(r\) items out of \(n\) in which the order matters.
Example5.4.9.
In how many ways can a president, vice president, secretary, and treasurer be selected from a 16-person club?
Solution.
We are finding how many arrangements of four people can be selected out of a total of 16. The order of selection matters because the four jobs are different. Therefore, we are finding the permutation \({}_{16}P_4\text{.}\)
Most scientific calculators have a permutation function. To find \({}_{16}P_4\) on a scientific calculator, we enter 16, then the permutation function, then 4.
, the permutation function is found in the func or functions area or by typing nPr, and both then \(n\) and \(r\) values are entered as arguments of the permutation function. To find \({}_{16}P_4\) in DESMOS, we enter nPr(16,4).
Subsection5.4.4Combinations
In the example above, we found that there were 43,680 different ways that four people out of a pool of 16 could be selected to fill four different positions. Consider now that the four people are being selected to serve as representatives and it doesn’t matter which person is selected first, second, third, or fourth. Each grouping of four people can be selected in \(4!=24\) different orders. In other words, each grouping of four people will appear 24 times in the 43,680 arrangements. Therefore, we can divide to find that the number of ways four people can be selected as representatives is \(\frac{43\,680}{24}=1820.\)
Looking back, what we calculated is \(\frac{16!}{(16-4)!\cdot4!}=1820.\) This is called a combination and is written \({}_n C_r =\frac{n!}{(n-r)!\cdot r!}.\) A combination represents the number of ways that a group of \(r\) objects can be selected from a pool of \(n\) without replacement and where the order they are selected doesn’t matter. We typically use combinations when finding probabilities related to card games because the order in which the cards are dealt doesn’t matter.
Combinations.
A combination is the number of ways to select \(r\) objects from a set of \(n\text{.}\)
Combinations are groups of \(r\) items out of \(n\) in which the order does not matter.
Combinations may also be read as "n choose r" because they are the number of ways to choose \(r\) objects from a set of \(n\text{.}\) You may also see a combination written as \(C(n,r)\) or \(\binom{n}{r}\text{.}\)
Example5.4.10.
How many five-card poker hands can be dealt from a standard 52-card deck?
Solution.
The order in which the cards are dealt does not matter, so we are looking for the number of combinations of five cards out of a total of 52. This is written as \({}_{52}C_5\text{.}\)
This value can also be calculated directly using the combination function on a scientific calculator.
Example5.4.11.
How many different five-card poker hands can be dealt from a standard 52-card deck that consist of all hearts, and what is the probability of being dealt such a hand?
Solution.
Since we want all five cards to be hearts, we are looking for the number of ways to choose five cards from the thirteen available hearts. This is written as \({}_{13}C_5\text{.}\)
The total number of five-card poker hands that can be dealt from a standard 52-card deck is \({}_{52}C_5=2\,598\,960\text{.}\)
Therefore, the probability of being dealt a hand of all hearts is \(\frac{1\,287}{2\,598\,960}\approx0.0495\%.\)
Example5.4.12.
There are 15 red marbles and 10 blue marbles in a bag. Suppose we will draw six marbles from the bag without replacement. What is the probability that all six marbles drawn are red?
Solution.
To find the probability that all six marbles drawn are red, we need to find the number of ways any six marbles can be drawn from the bag and the number of ways six red marbles can be drawn from the bag.
The total number of marbles is 15 + 10 = 25. The total number of ways to draw six marbles from the bag is \({}_{25}C_6=177\,100.\)
The number of ways to draw six red marbles from the bag is \({}_{15}C_6=5\,005.\)
Therefore, the probability of drawing six red marbles is \(\frac{5\,005}{177\,100}\approx2.83\%.\)
How do you know when to use the fundamental counting principle, permutations, or combinations when solving a problem?
When to Use Each Counting Method.
The fundamental counting principle can be used when you are making a series of decisions or random selections and:
The order of the decisions or random selections matters (AB is different from BA), or
The decisions or random selections are independent (the outcome of one decision or random selection does not affect the outcomes of the other decisions or random selections), or
Repetitions are allowed (e.g., each card is put back in the deck before the next card is drawn).
A permutation can be used when you are making a series of decisions or random selections and:
The order of the decisions or random selections matters (AB is different from BA), and
Repetitions are not allowed (e.g., each card is left out of the deck after it is drawn).
A permutation is a special case of the fundamental counting principle, so any application requiring a permutation could also be solved using the fundamental counting principle.
A combination can be used when you are making a series of decisions or random selections and:
The order of the decisions or random selections does not matter (AB is the same as BA), and
Repetitions are not allowed (e.g., each card is left out of the deck after it is drawn).
Example5.4.13.
Determine whether the fundamental counting principle, permutations, or combinations should be used to find the number of outcomes in each of the following scenarios. Then find the number of outcomes for each scenario.
How many different ways can the letters in the word "HELP" be arranged?
How many different outfits can be made if we have three shirts, two pairs of pants, and four pairs of shoes?
How many ways can we select three students from a class of 30 to be on a committee?
Solution.
The order of the letters matters, and the letters cannot be repeated, so we would use either a permutation or the fundamental counting principle.
There are four different letters, and we are arranging all four of them, so the number of arrangements is:
Subsection5.4.5More Applications Involving Combinations and the Fundamental Counting Principle
In the previous examples, we have only had to use one of the counting methods to find the number of outcomes for a scenario. However, some scenarios require multiple applications of the fundamental counting principle, combinations, and/or permutations together. For example, suppose we want to find the probability of drawing exactly three red marbles and three blue marbles from a bag containing 15 red marbles and 10 blue marbles. Using the fundamental couunting priciple, we can find the number of ways to draw three red marbles and three blue marbles as the product of the number of ways to draw three red marbles and the number of ways to draw three blue marbles:
\begin{equation*}
\text{(Ways to select the red marbles)} \cdot \text{(Ways to select the blue marbles)}
\end{equation*}
The number of ways to select items from multiple groups is the product of the number of ways to select items from each group.
Very often, this will be a product of combinations.
Example5.4.14.
There are 17 seniors, 20 juniors, and 15 sophomores in a high school band. Four of them wil be randomly selected to represent the band at a music festival. Read each question carefully and find the probability of the indicated outcome.
What is the probability that two seniors and two juniors will be selected?
What is the probability that two seniors, one junior, and one sophomore will be selected?
What is the probability that exactly one sophomore will be selected?
What is the probability that no sophomores will be selected?
Solution.
First, we find the total number of ways to select four representatives from the band. There are 52 total members of the band, so the total number of ways to select four representatives is \({}_{52}C_4=270\,725.\) This will be the denominator for each of the probabilities.
We are looking for two of the 17 seniors and two of the 20 juniors. This results in:
We are looking for exactly one of the 15 sophomores, which means the other three representatives must be selected from the 37 non-sophomores. This results in:
In the previous example, when finding the probability of exactly one sophomore being selected, we had to include the condition that the other three representatives must be selected from the non-sophomores. To ensure that you are including all the necessary conditions, it is helpful to check that the values of \(r\) in each factor of the numerator add up to the total number of representatives being selected. (Note that this is not a hard-and-fast rule, but it is a good way to check your work.) In this case, we are selecting four representatives, and the values of \(r\) in the numerator are 1 for the sophomores and 3 for the non-sophomores, which add to 4.
What if we wanted to find the probability of at least one sophomore being selected? One approach is to find the number of ways to select one sophomore and three non-sophomores, two sophomores and two non-sophomores, three sophomores and one non-sophomore, and four sophomores, adding these values together, and then dividing by the total number of ways to select four representatives. This results in:
However, it is simpler to find this probability using the complement. The event of at least one sophomore being selected is the complement of no sophomores being selected, which we found to have probability 24.4%. Therefore, the probability of at least one sophomore being selected is approximately \(100\%-24.4\%=75.6\%.\)
Probability of At Least One.
The complment of "at least one" is "none".
\begin{equation*}
P(\text{at least one})=100\% - P(\text{none})
\end{equation*}
or
\begin{equation*}
P(\text{at least one})=1-P(\text{none})
\end{equation*}
Example5.4.15.
A jury pool consists of 60 people, and 12 of them will be selected to serve on a jury. Of the 60 people in the pool, the highest level of education is shown in the table below. All members of the pool have at least a high school diploma.
Highest Education Level
Number of People
High School Diploma
20
Associate’s Degree
15
Bachelor’s Degree
15
Graduate Degree
10
What is the probability that at least one person with a graduate degree will be selected to serve on the jury?
Solution.
The probability of at least one person with a graduate degree being selected is the complement of no people with a graduate degree being selected. The number of ways to select any 12 people from the pool is \({}_{60}C_{12}\text{,}\) and the number of ways to select 12 people from the 50 people without a graduate degree is \({}_{50}C_{12}\text{.}\) Therefore, the probability that at least one person with a graduate degree will be selected to serve on the jury is approximately
Probabilities of this type are often used in determining whether there is evidence of discrimination in jury selection.
We will conclude this section with several examples from five-card poker. Notice that some of the "selections" involve two steps: first selecting a rank or suit and then selecting cards of that rank or suit. This means that the numerator may have additional factors or the \(r\) values in the numerator may sometimes be greater than five.
Example5.4.16.
Find the probability of being dealt a five-card poker hand with three kings and two jacks from a standard 52-card deck. Then find the probability of being dealt a full house, which is a five-card poker hand with three cards of one rank and two cards of another rank, from a standard 52-card deck. Finally, find the probability of being dealt three of a kind, which is a five-card poker hand with three cards of one rank and two additional cards of different ranks, from a standard 52-card deck.
Solution.
The number of ways to choose three kings from the four available is \({}_{4}C_3\text{.}\) The number of ways to choose two jacks from the four available is \({}_{4}C_2\text{.}\) By the fundamental counting principle, the total number of ways to be dealt a five-card poker hand with three kings and two jacks is:
There are 13 different ranks that the three of a kind could be and 12 different ranks that could be the pair. Therefore, the total number of ways to be dealt a full house is:
There is a 0.144% chance of being dealt a full house in five-card poker.
Example5.4.17.
Find the probability of being dealt three of a kind, which is a five-card poker hand with three cards of one rank and two additional cards of different ranks, from a standard 52-card deck.
Solution.
There are 13 different ranks that could be the three of a kind, and for each of these ranks, there are \({}_{4}C_3\) ways to choose the three cards. The two additional cards must be of different ranks than the three of a kind and different from each other, so there are \({}_{12}C_2\) ways to pick the ranks of the two additional cards and \({}_{4}C_1\) ways to choose each of these cards. Therefore, the probability of being dealt three of a kind is:
We have just shown that there is a 2.11% chance of being dealt three of a kind in five-card poker.
Example5.4.18.
Find the probablity of being dealt two pairs, which is a five-card poker hand with two cards of one rank, two cards of another rank, and one additional card of a different rank, from a standard 52-card deck.
Solution.
First, we choose the two ranks that will be the pairs. There are \({}_{13}C_2\) ways to do this. For each of these ranks, there are \({}_{4}C_2\) ways to choose the two cards of that rank. The additional card must be of a different rank than the pairs, so there are 11 remaining ranks to choose from and \({}_{4}C_1\) ways to choose the card of that rank. Therefore, the probability of being dealt two pairs is:
The type of reasoning use in this section can be applied to transportation and reservation logistics, molecular biology, and many other fields in addition to card games.
Exercises5.4.6Exercises
1.
How many different license plates are possible in the state of Washington if a license plate consists of three letters followed by three numbers between zero and nine?
