This section introduces several new terms and their notations. Factorial, permutations, and combinations will likely be completely unfamiliar, but they are based on math you already know. Flashcards and repetition with practice problems will help you obtain them.
Counting? You already know how to count or you wouldn’t be taking a college-level math class, right? Well yes, but what we’ll really be investigating here are ways of counting efficiently. When working with probability situations we will need to count some very large numbers, like the number of possible winning lottery tickets. One way to do this would be to write down every possible set of numbers that might show up on a lottery ticket, but believe me: you don’t want to do this.
Suppose at a particular restaurant you have three choices for an appetizer (soup, salad or breadsticks) and five choices for a main course (hamburger, sandwich, quiche, fajita or pizza).
If you are allowed to choose exactly one item from each category for your meal, how many different meal options do you have?
Solution 1: One way to solve this problem would be to systematically list each possible meal:
Assuming that we did this systematically and that we neither missed any possibilities nor listed any possibility more than once, the answer would be [latex]15[/latex]. Thus you could go to the restaurant [latex]15[/latex] nights in a row and have a different meal each night.
Solution 2: Another way to solve this problem would be to list all the possibilities in a table:
soup
salad
breadsticks
hamburger
soup + burger
salad + burger
breadsticks + burger
sandwich
soup + sandwich
ect.
quiche
soup + quiche
fajita
soup + fajita
pizza
soup + pizza
In each of the cells in the table we could list the corresponding meal: soup + hamburger in the upper left corner, salad + hamburger below it, etc. But if we didn’t really care what the possible meals are, only how many possible meals there are, we could just count the number of cells and arrive at an answer of [latex]15[/latex], which matches our answer from the first solution. (It’s always good when you solve a problem two different ways and get the same answer!)
Solution 3: We already have two perfectly good solutions. Why do we need a third? The first method was not very systematic, and we might easily have made an omission. The second method was better, but suppose that in addition to the appetizer and the main course we further complicated the problem by adding desserts to the menu: we’ve used the rows of the table for the appetizers and the columns for the main courses—where will the desserts go? We would need a third dimension, and since drawing [latex]3[/latex]-D tables on a [latex]2[/latex]-D page or computer screen isn’t terribly easy, we need a better way in case we have three categories to choose form instead of just two.
So, back to the problem in the example. What else can we do? Let’s draw a tree diagram:
This is called a “tree” diagram because at each stage we branch out, like the branches on a tree. In this case, we first drew five branches (one for each main course) and then for each of those branches we drew three more branches (one for each appetizer). We count the number of branches at the final level and get (surprise, surprise!) [latex]15[/latex].
If we wanted, we could instead draw three branches at the first stage for the three appetizers and then five branches (one for each main course) branching out of each of those three branches.
OK, so now we know how to count possibilities using tables and tree diagrams but what do we do if we have a really large number?
Let’s go back to the previous example that involved selecting a meal from three appetizers and five main courses, and look at the second solution that used a table. Notice that one way to count the number of possible meals is simply to number each of the appropriate cells in the table, as we have done above. But another way to count the number of cells in the table would be to multiply the number of rows [latex](3)[/latex] by the number of columns [latex](5)[/latex] to get [latex]15[/latex]. Notice that we could have arrived at the same result without making a table at all by simply multiplying the number of choices for the appetizer [latex](3)[/latex] by the number of choices for the main course [latex](5)[/latex]. We generalize this technique as the basic counting rule:
basic counting rule
If we are asked to choose one item from each of two separate categories where there are [latex]m[/latex] items in the first category and [latex]n[/latex] items in the second category, then the total number of available choices is [latex]m \cdot n[/latex].
This is sometimes called the multiplication rule for probabilities.
