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.
Alternatively, there are three bread choices. For each bread, there are two meat choices. This gives us \(3\cdot2=6\) bread and meat combinations. For each bread and meat combination, there are two cheese choices, resulting in a total of \(6\cdot2=12\) possible sandwiches.
In the example above, there were three choices: bread, meat, and cheese. There were three options in the first choice, two options in the second choice, and two options in the third choice. The total number of possible sandwiches that result is the product \(3\cdot2\cdot2=12.\)
We can generalize this approach to obtain 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 five vowels and five 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\,560\text{.}\)
We will see later in this chapter that this number represents the number of five-card poker hands that are possible.
Students may encounter \(0!\) when calculating some probabilities. In that situation, we use \(0!=1\text{.}\)
Suppose we have 25 books, and we want to arrange five of them on a display shelf. We can apply the fundamental counting principle to find the number of ways that can be accomplished. There are 25 choices for the first book, 24 remaining choices for the second book, and so on, resulting in \(25\cdot24\cdot23\cdot22\cdot21=6\,375\,600\) possible arrangements.
We can make use of factorials to streamline this calculation. In order to end up with just the first five factors of \(25!\text{,}\) we can "divide away" the remaining \(25-5=20\) factors which amount to \(20!\text{.}\) In other words, we can calculate \(\frac{25!}{20!}=6\,375\,600\) to find the answer more quickly.
In general, the 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 pulled from a set of \(n\text{.}\)
Permutations are groups of \(r\) items out of \(n\) in which the order matters.
Example5.4.8.
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. In DESMOS 1
www.desmos.com/scientific
, the permutation function is found in the func or functions area or by typing nPr. 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.
Example5.4.9.
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.10.
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\%.\)
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 counting principle together with combinations, we can find the number of ways to draw three red marbles and three blue marbles.
The number of ways to choose three red marbles from the 15 available is \({}_{15}C_3\text{.}\) The number of ways to choose three blue marbles from the 10 available is \({}_{10}C_3\text{.}\) By the fundamental counting principle, the total number of ways to draw three red marbles and three blue marbles is:
