3.2: Counting Strategies

Learning Objectives

• Use tree diagrams to organize outcomes in a series of activities
• Develop and use the Multiplication Rule for counting the number of possible outcomes, including the factorial method
• Develop and use the permutation method for counting the number of possible outcomes in ordered arrangements
• Develop and use the combination method for counting the number of possible outcomes in unordered arrangements

Outcomes from a Series of Activities

We have discussed the classical method of computing probabilities for an event \(A\) by the formula \[ \nonumber P\left( A \right) = \frac{\text{number of ways event }A \text{ can occur}}{\text{number of outcomes in the sample space}} = \frac{x}{n}, \]provided outcomes in the sample space are equally likely. The formula requires determining the total number of outcomes in the sample space and in \(A.\) Up to this point, our examples and exercises have dealt with reasonably small sample spaces; however, the number of outcomes of interest can be quite large. This section develops counting techniques that aid us in determining the number of possible outcomes. We begin by finding a logical way to organize the development of a sample space for multi-trial situations, such as tossing multiple dice. Ultimately, we will develop an important counting method.

Tree Diagrams and the Multiplication Rule for Counting

A tree diagram helps us list the various outcomes in a series of activities. To build a tree diagram, we list all outcomes of the first activity. Next to each of those listed outcomes, we branch to list all outcomes of the second activity. We branch off each of the second listed outcomes for the third activity, and so on. Eventually, all activities in the situation will be completed. Let us use a familiar example to build our first tree diagram. Suppose we wish to develop the sample space for rolling two dice. First, we list all the outcomes that may occur with the first die roll (the first activity of the described situation).

Figure \(\PageIndex{1}\): Tree diagram of first die roll

Next, from each of those six listed outcomes, we list all the outcomes that may occur with the second die roll (the second activity of the described situation).

Figure \(\PageIndex{2}\): Tree diagram of rolling two dice

Notice that, at the right of the diagram, we listed all thirty-six branches of the tree. This gives us an organized listing of the entire sample space. This branching idea hints at a counting strategy to determine the number of objects in the sample space. There are six branches for the first die roll and six branches from each for the second die roll; this leads to a total of \(6 \cdot 6\) \(=36\) outcomes in the sample space. This strategy is called the Multiplication Rule for Counting: if there are \(m\) possible outcomes for a first activity \(A_1\) and there are \(n\) possible outcomes for a second activity \(A_2,\) there are a total of \(m \cdot n\) possible outcomes for the experiment in which activity \(A_1\) is followed by activity \(A_2.\) This rule extends for any finite number of steps in a situation.

Text Exercise \(\PageIndex{1}\)

Create tree diagrams to determine the entire sample space of the following situations. Be sure to list the final sample space and then note the number of outcomes in the sample space.

1. A food truck allows customers to create a meal by selecting one item from each category: burger, side, and drink. There are three burgers to choose from \( \left( B_1, B_2, B_3 \right),\) two sides \( \left( S_1, S_2 \right),\) and three drinks \( \left( D_1, D_2, D_3 \right).\) Create the sample space of different meals that can be ordered from this food truck.

Answer

We create the tree diagram as shown below. Notice that our first level of branches are the three burger choices, the second level of branches are the two side choices, and the third level of branches are the three drink choices:

Figure \(\PageIndex{3}\): Tree diagram of food truck meals

Notice that our diagram gives us our sample space. \begin{Bmatrix} B_1\sim S_1\sim D_1,~B_1\sim S_1 \sim D_2,~B_1\sim S_1\sim D_3, \\ B_1\sim S_2\sim D_1,B_1\sim S_2\sim D_2,~B_1\sim S_2\sim D_3, \\B_2\sim S_1\sim D_1,~B_2\sim S_1 \sim D_2,~B_2\sim S_1\sim D_3, \\ B_2\sim S_2\sim D_1,B_2\sim S_2\sim D_2,~B_2\sim S_2\sim D_3, \\ B_3\sim S_1\sim D_1,~B_3\sim S_1 \sim D_2,~B_3\sim S_1\sim D_3, \\ B_3\sim S_2\sim D_1,B_3\sim S_2\sim D_2,~B_3\sim S_2\sim D_3 \nonumber\end{Bmatrix}The sample space consists of \(18\) total outcomes. The Multiplication Rule of Counting predicts the total number of outcomes to be \(3 \cdot 2 \cdot 3\) \(= 18.\)

2. There are six tiles well-mixed in a bag. The tiles are identical except in color; three are red, two are white, and one is blue. We are to randomly draw two tiles from the bag, one at a time, without replacement. Produce the sample space of two tiles that can be drawn from the bag.

Answer

Again, we can create the diagram, but we must think clearly about each step of tile selection since the choices available for the second tile selection depend on what happened in the first tile selection. Since the tiles are identical, we cannot distinguish between those tiles of the same color. We might draw any of the three colors in the first tile selection, but in the second tile selection, we cannot select blue if we have selected blue on the first draw. We can organize our listing to produce the following tree diagram.

Figure \(\PageIndex{4}\): Tree diagram of tile combinations

The final sample space is \begin{Bmatrix} red \sim red,~red \sim white ,red \sim blue, \\ white \sim red,~white \sim white ,white \sim blue, \\blue \sim red,~blue \sim white \nonumber\end{Bmatrix}which includes \(8\) total outcomes. Notice how our Multiplication Rule of Counting must be carefully used because we cannot select the blue tile again. There were two colors (specifically red and white) that, if selected first, still allowed three colors to be chosen in the second selection. There was one color (specifically blue) that, if selected first, only allowed two colors to be chosen in the second selection. We can adjust the rule's application so that \(2 \dot 3\) \(+ 1 \cdot 2\) \(= 8 \) predicts the total number of outcomes in the sample space.

3. A salesman must visit four important clients: Mr. White, Miss Scarlet, Professor Plum, and Mrs. Peacock. Determine the number of choices the salesman has to visit these clients.

Answer

We create the tree diagram as shown below, which gets a bit large. (One thing we might consider is to give codes to the four clients, such as numbering them \(1\) to \(4\) and using the numbers instead of their longer names.) The tree is reasonably easy to produce if we maintain our organization while creating each branch level, one at a time.

Figure \(\PageIndex{5}\): Tree diagram of client visits

In this situation, we will not list the sample space of \( 24\) distinct outcomes since it can be seen in the last column of the tree diagram. Notice how our Multiplication Rule of Counting predicts the number of outcomes at \( 4 \cdot 3 \cdot 2 \cdot 1 = 24 \). We have \(4\) options for the first visit, \(3\) options for the second, \(2\) options for the third, and then only \(1\) options for the final visit.

In our examples of tree diagrams, we can begin counting the number of outcomes by using our multiplication rule, but we must consider what happens at each branching action of the tree. Once we become comfortable with the concept of the multiplication rule, we can more quickly compute the number of possible outcomes.

First Basic Counting Techniques

We have shown that the Multiplication Rule for Counting is a valuable tool for determining the number of possible outcomes in many situations. We now use this tool to develop general counting techniques without producing tree diagrams. As we develop various techniques, remember that all the methods are developed from the Multiplication Rule for Counting.

Suppose June buys a new cell phone and must choose a six-digit code to keep it secure when she is not using it. How safe is her phone from someone who randomly chooses six digits to unlock it? Knowing that June will select one, we need to determine the number of possible six-digit codes. The standard convention in choosing a code allows for digits to repeat. Later, we will see what happens if the code cannot use digits more than once. We can think through the branching of a tree diagram using a simple counting diagram to determine the number of outcomes possible, \begin{matrix}\nonumber \text{# of Possibilities}&\text{ ___ }& \text{ ___ } & \text{ ___ } & \text{ ___ } &\text{ ___ } & \text{ ___ }&\, \\ \text{Choices for} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} & 6^{th} & \text{Code digit position} \end{matrix}where the row of blanks represent the numbers to be chosen in the given position in the code. We only need to place the number of possibilities in each blank for each code position. Recall that there are ten digits, \(0\) to \(9,\) and with use of the multiplication rule, we have \begin{matrix} \nonumber \text{# of Possibilities}&\underline{\, 10\, }& \underline{\, 10\,} & \underline{\, 10\,} & \underline{\, 10\,} &\underline{\, 10\,} & \underline{\, 10\, }&\Rightarrow 10 \cdot 10\cdot 10\cdot 10\cdot 10\cdot 10=10^6=1,000,000 \\ \text{Position} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} & 6^{th} & \, \end{matrix}There are \(1,000,000\) unique codes that June could choose from. The probability of someone randomly guessing June's code is \(P(\small{\text{GUESSING }}\)\(\small{\text{CODE}})\normalsize\)\( = \frac{1}{1,000,000}\)\( = 0.000001.\) This event is highly unlikely; June should feel relatively safe about someone randomly guessing her code. We would not want to construct the sample space in this situation due to the number of outcomes possible, yet we can still reflect on the sample space and know how many codes are in the sample space.

In Text Exercise \(\PageIndex{1}.3\) regarding a salesman visiting four distinct clients, we can use a similar approach: \begin{matrix}\nonumber \text{# of Possibilities}&\text{ ___ }& \text{ ___ } & \text{ ___ } & \text{ ___ } &\, \\ \text{Choices for} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & \text{Client visit position} \end{matrix}where the row of blanks represent the order to visit the four clients. We know that we have four clients to choose from in the first position; once that choice is made, there are three clients left to choose from for the second position; similarly, there are just two clients left to choose for the third position; and finally, only one client will be left for the fourth position: \begin{matrix} \nonumber \text{# of Possibilities}&\underline{\, 4\, }& \underline{\, 3\,} & \underline{\, 2\,} & \underline{\, 1\,} &\Rightarrow 4 \cdot 3 \cdot 2 \cdot 1 =24 \\ \text{Position} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & \, \end{matrix}There are \(24\) unique orderings the salesman could choose for visiting the four clients. This last example is a multiplication pattern that frequently occurs in counting outcomes. The shortened notation for this computation is called the factorial notation \(4!.\) The \(!\) symbol is read "factorial", \(4!\) is read "four factorial", and \(4!\) means, computationally, \(4 \cdot 3\cdot 2\cdot 1.\) In general \(n!\) represents the product \(n(n-1)(n-2)\cdot\ldots\cdot 2\cdot 1.\) We assign \(0! = 1\) by special definition. Notice how quickly factorials increase in value; for example \(8!\) \(= 40,320\) and \(20!\) \(= 2.4329 \times 10^{18}.\) Try the text exercises below for more practice with counting the number of possible outcomes.

Text Exercise \(\PageIndex{2}\)

Determine the total number of outcomes possible for each of the given descriptions.

1. We have five standard fair coins of different values: a penny, a nickel, a dime, a quarter, and a half-dollar. When tossed, each lands on heads (H) or tails (T). One way they might land, in order of increasing value, is HHTHT.
   1. How many ways can the coins land when tossed and placed in order of value, say from smallest value to largest?
   2. How many ways can we order the five different coins?

Answer

Both parts of this question ask for a count, and we use the multiplication rule for each, though the results are different.

1. We establish our simple counting diagram, remembering that the coins are placed in order of increasing value: \begin{matrix}\nonumber \text{# of Possibilities}&\text{ ___ }& \text{ ___ } & \text{ ___ } & \text{ ___ } & \text{ ___ } &\text{each coin's landing side} \\ \text{Position of Coins} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} &\text{by denomination} \end{matrix} then we notice that each trial has two possible outcomes, either H or T. Our counting diagram becomes \begin{matrix} \nonumber \text{# of Possibilities}&\underline{\,2\, }& \underline{\, 2\,} & \underline{\, 2\,} & \underline{\, 2\,} & \underline{\, 2\,} &\Rightarrow 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 2^5 =32 \\ \text{Position} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} & \, \end{matrix}This tells us there are \(32\) possible head and tail arrangements.
2. Next, we examine the number of ways the five distinct coins can be placed in an order, such as from smallest value to largest, largest to smallest, or even some other arrangement. It is important to note that each of the coins is distinguishable from the other, so there is no confusion on which coin is in which location. We establish our simple counting diagram as an aide: \begin{matrix} \nonumber \text{# of Possibilities} & \text{ ___ } & \text{ ___ } & \text{ ___ } & \text{ ___ } & \text{ ___ } &\, \\ \text{Position in Arrangement} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} &\text{by coin denomination} \end{matrix} and see there are five choices for a coin to be placed in the \(1^{st} \) position. Once that coin is chosen, we have only four choices for the coin in the second position, and so on. Our counting diagram becomes \begin{matrix} \nonumber \text{# of Possibilities}&\underline{\,5\, }& \underline{\, 4\,} & \underline{\, 3\,} & \underline{\, 2\,} & \underline{\, 1\,} &\Rightarrow 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1= 5! = 120 \\ \text{Position} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} & \, \end{matrix}This tells us there are \(120\) possible arrangements of the coins by denomination. In the upcoming optional section, we will revisit this situation, in which some of the coins are not distinguishable from each other, requiring adjustments in our counting method.

2. There are two distinctly colored standard decks of playing cards (red and blue). How many different outcomes are possible if we draw four cards in sequence, with two cards drawn first from the red deck and then two more from the blue deck?

Answer

We again establish our simple counting diagram: \begin{matrix}\nonumber \text{# of Possibilities}&\text{ ___ }& \text{ ___ } & \text{ ___ } & \text{ ___ } &\, \\ \text{Choices for} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} &\text{each card's position} \\ \, & \text{red } & \text{cards} & \text{blue} & \text{cards}& \, \end{matrix}then we determine the possible outcomes for each card position. Our counting diagram becomes \begin{matrix} \nonumber \text{# of Possibilities}&\underline{\,52\, }& \underline{\, 51\,} & \underline{\, 52\,} & \underline{\, 51\,} &\Rightarrow 52 \cdot 51 \cdot 52 \cdot 51 = 7,033,104 \\ \text{Position} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & \, \\ \, & \text{red } & \text{cards} & \text{blue} & \text{cards}& \, \end{matrix}That is over \(7\) million different possible outcomes! We are definitely glad we did not have to produce the entire sample space for this simple little situation.

3. Leisha is a research biologist for a sod (grass) company. She must research the effects of four fertilizer types on three temperature zones with three watering amounts. How many different sod plots must she create to test all possible configurations of these three factors?

Answer

We jump to the final computing action to tell Leisha how many plots she will need to perform her research: \begin{matrix}\nonumber \text{# of Possibilities}&\underline{\,4\, }& \underline{\, 3\,} & \underline{\, 3\,} &\Rightarrow 4 \cdot 3 \cdot 3 = 36 \\ \text{Factor Choice} & \text{fertilizer} & \text{temp. zones} & \text{water amts.} &\, \end{matrix}Leisha will need to have \(36\) different plots for her desired sod research.

4. Carl is a psychologist studying telepathy between patients who claim such abilities. He will test their claims using a deck of six cards, each with a different picture. The cards will be shuffled randomly before each pair of patients uses the cards in his experiment. How many different card arrangements (shuffled decks) are possible?

Answer

Again, we jump to the final computing action to answer Carl's dilemma:\begin{matrix}\nonumber \text{# of Possibilities}&\underline{\,6\, }& \underline{\, 5\,} & \underline{\, 4\,} & \underline{\, 3\,} & \underline{\, 2\,} & \underline{\, 1\,} &\Rightarrow 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 6! = 720 \\ \text{Card deck position} & 1^{st} & 2^{nd} & 3^{rd} & 4^{th} & 5^{th} & 6^{th} &\, \end{matrix}So Carl will have \(6!\) \(=720\) different card arrangements possible in the deck of six cards. We mention that this is a factorial count situation. Once we recognize a factorial count, we will reach the final answer of \(6!\) with no diagram work. We note for Carl that if the probability of one patient in the study randomly guessing all six cards correctly as examined only by their telepathy partner is \( \frac{1}{720}\) \(\approx 0.1389%\)--not impossible but highly improbable.

Counting with Permutations

Suppose, in the last problem from Text Exercise \(\PageIndex{2},\) Carl selected only three of the six cards for his patients to test their telepathic abilities. We can still use the same method described above. \begin{matrix}\nonumber \text{# of Possibilities}&\underline{\,6\, }& \underline{\, 5\,} & \underline{\, 4\,} &\Rightarrow 6 \cdot 5 \cdot 4 = 120 \\ \text{Card deck position} & 1^{st} & 2^{nd} & 3^{rd} &\, \end{matrix}Carl will have \(120\) different smaller deck arrangements if only selecting any three of the six original cards for the smaller deck.

More formally, we call situations that are counted this way permutations. A permutation count is the number of ways to arrange, in order, \(n\) distinct objects, taking \(r\) at a time. We denote this symbolically as \( \sideset{_{n}}{_{r}}P\) where \(n\) and \(r\) are whole numbers with \(n \ge r.\) The two general forms for computing this count are given by:\[ \begin{align*}\hspace{1in}\sideset{_{n}}{_{r}}P &=n(n-1)(n-2) \cdots (n-r+1) \hspace{1in}&&(1)\\&=\dfrac{n!}{(n-r)!}&&(2) \end{align*}\]When building the counting action, we tend to use \((1).\) When working with permutations theoretically, we tend to represent permutation counts using \((2).\) We should become familiar with both forms of computing permutations. Using Carl's smaller deck we can see the computation as \[ \nonumber \sideset{_6}{_3}P =n(n-1)(n-2) \cdots (n-r+1)= 6 \cdots (6 - 3 +1) = 6 \cdot 5 \cdot 4=120 \\ \text{and also} \\ \sideset{_{6}}{_{3}}P =\frac{n!}{(n-r)!}= \frac{6!}{(6-3)!}=\frac{6 \cdot 5 \cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3} \cdot \cancel{2} \cdot \cancel{1}}=120\]Our fraction form of computation with factorials is canceling out the unused \((n-r)!\) objects in the count from the \(n!.\) We also want to quickly recognize situations requiring permutation counts (especially when large numbers are involved) so we can use technology to perform the calculations.

Text Exercise \(\PageIndex{3}\)

Determine the number of outcomes possible in the described situations:

1. Matching questions are sometimes used in statistics exams. If ten distinct statistical symbols are to be matched uniquely with ten distinct statistical terms, how many symbols-to-terms matches (correct or incorrect) are possible?

Answer

We could use a counting diagram, but we produce the counts by recognizing the strategies discussed without using a diagram in these answers. Thinking about our statistical term choices for each of the ten symbols, we see there are \(10 \cdot 9 \cdot 8 \cdots 2 \cdot 1\) \(=10!\) \(= 3,628,800\) different symbol-to-term matches students can make. A student strictly randomly guessing all ten correctly has a probability of only \(\frac{1}{3,628,800}\) \(\approx 0.0000002756.\) We recognize that this count is not only a simple factorial count but that any factorial count can be considered a permutation count. Specifically \(10!\) \(=\sideset{_{10}}{_{10}}P\) \(=\frac{10!}{(10-10)!}.\)

2. In the same matching question used above, if there are only seven distinct statistical symbols to be matched with the given ten distinct statistical terms, how many symbols-to-terms matches might be made by students?

Answer

In this case, we only match seven symbols (places) with ten terms (objects). There are \( 10 \cdot 9 \cdots 4\) \(= \sideset{_{10}}{_{7}}P\) \(= 604,800 \) different symbol-to-term matches that students can make. After a little thought, we should recognize that this is a permutation counting situation since the order is important.

3. A saleswoman must visit only four of her nine clients tomorrow. How many different ordered client visit lists can the saleswoman make?

Answer

At this point, we recognize quickly that this is also a permutation count since order matters. The saleswoman has \( \sideset{_{9}}{_{4}}P\) \(= 3,024 \) ordered client visit lists that she might make. We doubt she will make all these, but knowing how many are possible speaks to the variety of ordered lists she has available. We can also use technology to compute such permutation values after we note the values of \(n\) and \(r.\) For example, in an Excel spreadsheet cell, we can enter \(=\text{PERMUT}(9, 4)\) and the value \(3024\) will be shown.

4. During a two-hour time frame, a nurse must take vital signs measurements from ten of his forty assigned patients. How many different lists can the nurse make for an ordered round involving ten of the forty patients?

Answer

We quickly recognize that this is also a permutation count. The nurse has \( \sideset{_{40}}{_{10}}P \) ordered patient lists that he might make for his two-hour round. We will use technology for the computation: in an Excel spreadsheet cell, we can enter \(=\text{PERMUT}(40,10)\) producing the approximate value \(3.07599\)E+\(15;\) this is a standard technology representation of the number \( 3.07599 \times 10^{15}.\) He can make well over a quadrillion ordered patient lists in this situation. We might be amazed at the possibilities and appreciate how many randomly chosen ordered lists can be made.

5. We return to our "Birthday" problem of Text Exercise \(3.1.5,\) which asks, "What is the probability that in a random group of thirty-five people, two or more of the group will share a birth day in the year (such as September \(1^{st}\) or May \(28^{th}\))?" To answer this question, we assume \(365\) days in a year (ignore leap year cases), that each day of the year is equally likely for births, and the birth day of the various individuals in the group is not dependent on another individual in the group.

Answer

We first note that in a group of thirty-five people placed in some order, the first person will have one of \(365\) different birth days, the second will have one of \(365\) birth days, ... ,the thirty-fifth will have one of \(365\) birth days. There are \( 365^{35}\) \(\approx 4.7891 \times 10^{89} \) possible lists of thirty-five birth days that various groups of thirty-five people can form.

Now, we must find how many of those lists have two or more with the same birth day in the year. To do so, we must look at many separate cases: how many of our lists have exactly two in a birth day list the same or how many have precisely three the same or ... or how many have all thirty-five with the same birth day or how many have two different pairs the same or...etc. But being reflective on the work in finding so many separate counts and being wise to consider other methods, we again notice that there is only one case in the complement description: having lists in which none of the thirty-five have the same birth date. The use of the complement method makes this problem approachable. Therefore, we must count only the number of lists of birth days that can be made in which none of the thirty-five are the same birth day.

Since this is an ordered list, we recognize this is a permutation count in which we are forming lists of \(35\) distinct birth days coming from \(365\) options...that is, we need \( \sideset{_{365}}{_{35}}P\) \(= \frac{365!}{(365 - 35)!}\) \(\approx 8.8893 \times 10^{88}.\) So, \(P(\small{\text{NONE }}\)\(\small{\text{HAVE }}\)\(\small{\text{THE }}\)\(\small{\text{SAME }}\)\(\small{\text{BIRThDAY}}\normalsize)\) \( \approx \frac{8.8893 \times 10^{88}}{4.7891 \times 10^{89}}\) \( \approx 0.1856.\)

Now, the \(P (\small{\text{AT }}\)\(\small{\text{LEAST }}\)\(\small{\text{TWO }}\)\(\small{\text{WITH }}\)\(\small{\text{SAME }}\)\(\small{\text{BIRTHDAY}})\)\(=1-P(\small{\text{NONE }}\)\(\small{\text{HAVE }}\)\(\small{\text{THE }}\)\(\small{\text{SAME }}\)\(\small{\text{BIRTHDAY}})\) \( \approx 1 - 0.1856\) \(=0.8142\) \(=81.42\%.\) Notice that in a randomly selected group of thirty-five people, there is a reasonably high probability that at least two will share the same birth day.

It is important to note that order is essential in permutations. Choosing object \(a\) and then object \(b,\) in that order, is counted as a different outcome from choosing object \(b\) first and then object \(a.\) When the order of choice is irrelevant (such as the saleswoman choosing to visit four of her nine clients but not concerned with the order of those of her visits), an adjusted approach must be taken: a counting approach termed as a combination.

Counting with Combinations

In each of our previous counting approaches, the order of selection was important to the counting. However, there are times when order is not important to the outcomes of an experiment, especially when we consider samples taken from a population. We begin with a simple, small example that we will later generalize.

Suppose we have four distinct individuals, Adam \( ( \text{A} ),\) Betsy \( ( \text{B} ),\) Cathy \( ( \text{C} ),\) and Damon \( ( \text{D} )\) and we wish to form all possible sample groups of size three from this population of four. Using our tree approach, we can create the \( \sideset{_{4}}{_{3}}P\) \( = 24 \) ways to arrange these four into ordered groups of three--yes, a permutation count. This list is given by: \begin{matrix} \nonumber \color{red} \text{ABC} & \color{blue} \text{DBC} & \color{gray}\text{ACD} & \text{ABD} \\ \color{red}\text{ACB} & \color{blue}\text{DCB} & \color{gray}\text{ADC} & \text{ADB} \\ \color{red}\text{BCA} & \color{blue}\text{BCD} & \color{gray}\text{CDA} & \text{BDA} \\ \color{red}\text{BAC} & \color{blue}\text{BDC} & \color{gray}\text{CAD} & \text{BAD} \\ \color{red}\text{CAB} & \color{blue}\text{CDB} & \color{gray}\text{DAC} & \text{DAB} \\ \color{red}\text{CBA} & \color{blue}\text{CBD} & \color{gray} \text{DCA} & \text{DBA} \end{matrix}The order displayed here is intentionally a bit different from our standard tree approach. Thinking back on our need to count how many sample groups of size three are available, we should note that the various colored collections of the ordered groups produce the same (unordered) sample groups. The first column of six shown in red is different arrangements of the same sample group containing Adam, Betsy, and Cathy; the second column of six in blue contains only one sample group of Betsy, Cathy, and Damon; the third column has the one sample group of Adam, Cathy, and Damon; and the fourth column of Adam, Betsy, and Damon. Given any collection of three individuals, we know there are \(3 \cdot 2 \cdot 1\) \(= 6\) ways to arrange those three. There are only \( \frac{ \sideset{_{4}}{_{3}}P }{3!}\) \(= \frac{24}{6}\) \(= 4\) unique sample groups (unordered groups) of size three from this collection of four individuals.

Is there a predictable pattern to develop a counting formula for the number of distinct unordered groups of size \(r\) taken from a collection of \(n\) distinct objects? First, we performed a permutation count of \( \sideset{_{n}}{_{r}}P \) to get the total number of ordered groups of size \(r\) taken from the \(n\) objects. Then, we had to divide by the number of ways any specific group of size \(r\) could be arranged--a factorial value of \(r!\)--to account for the same collection arranged differently. We computed \( \frac{ \sideset{_{n}}{_{r}}P }{r!} \) to determine the number of distinct combinations of \(n\) distinct objects taken \(r\) at a time. We call this type of counting a combination and denote in symbols as \( \sideset{_{n}}{_{r}}C \) or as \( \left( \begin{matrix} n \\ r \end{matrix} \right) \); in this text, we will use the \( \sideset{_{n}}{_{r}}C \) form for consistency. We typically read this as, "\(n\) choose \(r\)" since it is counting how many ways we can choose \(r\) objects from a group of \(n\) objects. We can express the formula for combination count in two ways.\[ \nonumber \left( \begin{matrix} n \\ r \end{matrix} \right) = \sideset{_{n}}{_{r}}C = \dfrac{ \sideset{_{n}}{_{r}}P }{r!}=\dfrac{n!}{(n-r)!r!}\]We can reason algebraically how the second formula is produced from the first by remembering that \( \sideset{_{n}}{_{r}}P\) \(= \frac{n!}{(n-r)!}.\) Many computing technologies also have built-in functions to relieve us from mechanical computation once we have recognized a counting situation as a combination. In the Excel spreadsheet, this function is \(=\text{COMBIN}(n,r).\)

We must remember that a combination counts the number of ways to form groups of size \(r\) from a collection of size \(n\) where order within the groups does not matter. Let us do one more example before a collection of text exercises. Suppose a committee of four students must be formed from a class of thirty-five distinct students. How many committees could be formed? Rearranging the order of four students does not create a different committee. Therefore, we must count using combinations. There are \( \sideset{_{35}}{_{4}}C\) \(= \frac{ \sideset{_{35}}{_{4}}P }{4!}\) \(=\frac{35 \cdot 34 \cdot 33 \cdot 32}{4 \cdot 3 \cdot 2 \cdot 1}\) \(= 52,360\) different possible committees of size four that could be formed from the thirty-five students. Using the Excel command \(=\text{COMBIN}(35,4)\) produces this same value of \(52,360.\)

Text Exercise \(\PageIndex{4}\)

Determine the number of outcomes possible in the described situations (warning: not all are combination counts).

1. A construction manager must select eight samples from a group of twenty concrete trucks to test the quality of the concrete mixture. How many different groups of eight can be selected?

Answer

Notice that initially, there are twenty trucks to choose between for the first sample, nineteen for the second, and so on until all eight needed trucks are chosen. However, we also recognize that once a group of eight trucks is selected in a specific order, rearranging those eight trucks in a different order will not create a different sample group. This is a combination counting situation, so we compute \(20\) choose \(8:\)\[ \nonumber \sideset{_{20}}{_{8}}C =\frac{20!}{(20-8)! \cdot 8!} = \frac{20 \cdot 19 \cdot 18 \cdot 17 \cdot 16 \cdot 15 \cdot 14 \cdot 13}{ 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 125,970.\]There are almost \(126,000\) sample groups of concrete trucks possible for the construction manager to choose. We could also have computed our value in a spreadsheet using \(=\text{COMBIN}(20,8)\) in a cell, producing this same end value of \(125,979.\)

2. A dial-faced combination lock produced by a new manufacturer uses three distinct numbers in the lock code between \(0\) and \(39.\) How many different lock codes are available?

Answer

In this case, we are choosing three numbers from a list of forty\( (0\) to \(39).\) We also recognize that once a group of three numbers is chosen, rearranging those three numbers will create a different lock code. This is a permutation counting situation, so we compute \(40\) permute \(3\):\[ \nonumber \sideset{_{40}}{_{3}}P =\frac{40!}{(40-3)!} = 40 \cdot 39 \cdot 38 = 59,280.\]There are \(59,280\) lock codes for the described lock. We should notice that the term "combination lock" does not use the term "combination" in the same fashion as our counting method; that is, the number of unlock codes for a combination lock is not determined by a combination counting strategy. Others' general use of the term "combination" may not align with our use of the term in counting strategies. We also note the computation in a spreadsheet using \(=\text{PERMUT}(40,3)\) in a cell produces this same computed value of \(59,280.\) For the remainder of our examples, we will use the spreadsheet for computation work after determining the type of counting method needed.

3. A qualified applicant pool for a large hospital's eight nurse trainee positions consists of ten women and six men.
   1. How many different groups of these sixteen applicants can be formed for the eight positions?
   2. How many different groups can be selected from the pool of applicants that consist entirely of women?
   3. If all applicants are considered equally qualified, and the group of eight positions is randomly selected, what is the probability that the chosen group will consist entirely of women? (This measure could be of interest in a "discrimination" claim if the chosen pool consisted only of women.)

Answer

In this situation, we have sixteen applicants; eight are needed to form our trainee group.

1. We recognize that we are choosing eight from our group of sixteen, and the order of arrangement of any group of eight will not make a different trainee group. This is a combination counting situation, so we compute \(16\) choose \(8.\)\[ \nonumber \sideset{_{16}}{_{8}}C = \text{COMBIN}(16,8)=12,870\]There are well over \(10,000\) trainee groups that can be formed from the pool of applicants.
2. For the selected group to be all women, we recognize that we are choosing eight from our group of ten women. We again notice that the order of arrangement of any group of eight women will not make a different trainee group; the selection order does not matter. This is a combination counting situation; we compute \(10\) choose \(8.\)\[ \nonumber \sideset{_{10}}{_{8}}C = \text{COMBIN}(10,8)=45\]There are \(45 \) trainee groups that can be formed only from the pool of women applicants.
3. Assuming random selection in which any group of eight is equally likely to be chosen, the probability that the selected group will consist entirely of women is \( P(\small{\text{ALL }}\)\(\small{\text{WOMEN}}\normalsize)\) \(=\frac{45}{12,870}\) \( \approx 0.3497\%,\) which we would consider an unusual event.

4. To win a specific Powerball lottery grand prize, a player must match all \(5\) white balls (order does not matter) and the red Powerball on his purchased ticket. There are \(69\) white balls labeled \(1\) to \(69\) and \(26\) red balls labeled \(1\) to \(26.\)
   1. How many different tickets could be purchased for entry into this type of Powerball lottery game?
   2. Knowing there is only one winning ticket per game, what is the probability that a randomly generated ticket will be the winning ticket for the grand prize?

Answer

Notice that initially, we can see two steps in this activity of completing an entry to the Powerball game. We choose five numbers from a list of sixty-nine and then select one number from a list of twenty-six. We use our multiplication rule between the counts of the two steps.

1. For the first step, we choose any five of the sixty-nine white-ball numbers, recognizing that once a specific group of five numbers is selected, rearranging those five chosen numbers will not make a different Powerball ticket. This is a combination counting situation, so we compute \( \sideset{_{69}}{_{5}}C\) \(= 11,238,513 .\) For the second step, we choose any of the twenty-six red-ball numbers, with a count of \(26\) possible choices. (We could do a combination count of \( \sideset{_{26}}{_{1}}C\) \(= \text{COMBIN}(26,1)\) as well, but this still produces that same value of \(26\) and involves unnecessary computation work. Thinking as we make our counts is more valuable than computation work.) There are a total of \( \sideset{_{69}}{_{5}}C \cdot 26\) \9= 292,201,338 \) possible tickets that could be made for any single Powerball lottery game.
2. Assuming a random selection of numbers for the winning ticket, the probability that a randomly generated ticket will be the winning ticket is \( P(\small{\text{WINNING }}\)\(\small{\text{TICKET}}\normalsize)\) \(=\frac{1}{292,201,338}\) \( \approx 3.4223 \times 10^{-9}.\) As we are probably all aware, winning a Powerball Lottery game by purchasing a single ticket is a highly unusual event. With these large numbers, we can also reason that we cannot create and purchase all possible tickets to guarantee winning.

Section Summary

This section on counting has been extensive. As a final review, let us list our various counting strategies.

1. Tree diagram (useful for creating and listing all possible outcomes for a situation in which multiple steps are used to produce the branches of the trees).
2. Multiplication Rule for Counting
3. Factorial Rule for Counting
4. Permutation Rule for Counting
5. Combination Rule for Counting

Knowing which counting method applies requires us to think clearly about the selection of the objects in steps and to determine if the order of selection matters to the count.