Skip to main content

Discrete Mathematics for Computing (Draft)

Christine Caples, Adam Gilbert, Melanie Fraser

Section 4.2 The Fundamental Principle of Counting

In this very short section we build on those very small-scale examples in the Counting Basics section and develop the Fundamental Principle of Counting. Like the previous section, we’ll develop mastery through a series of examples with increasing level of difficulty.

Subsection 4.2.1 Motivation

In the previous section, we considered atomic processes, which we described as processes which couldn’t be broken down into smaller, sub-processes. Examples of these atomic events were the roll of a single die or the flip of a coin, but not the rolling of a die and flipping of a coin. Indeed, rolling a die and flipping a coin is not an atomic process because it consists of two sub-processes (the rolling of the die and the flipping of the coin). In this section, we consider how to count the number of outcomes possible for this more complex process, and other complex processes too.
Let’s start by considering the process of rolling a fair, six-sided die and then flipping a coin, as described above and in the previous section. There are six outcomes possible from the die roll. Those are depicted in the image on the left, below. For each of the six possible outcomes of the die roll, there are two possible outcomes of the coin flip. A tree depicting possible outcomes from the entire process (coin flip and then die roll) appears on the right, below.
A tree showing the six possible outcomes from the roll of a single, six-sided die.
Figure 4.2.1. A tree of outcomes for a die roll.
A tree showing the twelve possible outcomes from the roll of a single, six-sided die followed by the flip of a coin.
Figure 4.2.2. A tree of outcomes for a die roll and subsequent coin flip.
Notice that for each of the six possible outcomes of the die roll, there are two possible coin flip outcomes. That is, the number of outcomes possible from the die roll and coin flip process is \(6\cdot \left(2\right) = 12\text{.}\)

Subsection 4.2.2 The Fundamental Principle of Counting (and Examples)

The multiplicative approach at the end of the previous subsection works in general. The following fact, labeled the Fundamental Principal of Counting, summarizes this idea.
Let’s work through one example using the Fundamental Principle of Counting and then you’ll have an opportunity to test your understanding by completing several embedded examples.

Example 4.2.4. Ordering From a Restaurant.

You are out to eat with some friends at a restaurant. This particular restaurant has a relatively small menu, but every order comes with an entree, a drink, and a dessert. The menue has seven different entrees, five different drinks, and four different dessert options. How many different orders are possible?
Answer.
Notice that there are seven (7) options for an entree, five (5) options for a drink, and four (4) options for dessert. For every choice of entree, there are five options for a drink, and for every combination of entree and drink there are four optons for dessert. Using the Fundamental Principle of Counting, the total number of orders is the product of the number of entrees, number of drinks, and number of desserts. That is, the number of orders is \(\boxed{\displaystyle{7\cdot\left(5\cdot 4\right) = 140}}\text{.}\)
Now you try! Use what you’ve learned to complete the following examples.

Checkpoint 4.2.5. Rolling Several Dice.

Checkpoint 4.2.6. Pizza Shop, Part I.

Checkpoint 4.2.7. Choosing a PIN (I).

Checkpoint 4.2.8. Pizza Shop, Part II.

The first part of this problem involves the Fundmental Principle of Counting -- use what you know to answer it. We won’t cover probability until a later chapter in this book. The probability of an event is the number of ways that event can occur divided by the total number of outcomes possible. Can you use the Fundamental Principle of Counting twice to solve the second part?

Checkpoint 4.2.9. Creating "Words" from an Alphabet.

Checkpoint 4.2.10. Choosing a PIN (II).

Checkpoint 4.2.11. Race Finishers.

The first two parts of this problem involve the Fundmental Principle of Counting -- use what you’ve learned to answer them. We won’t cover probability until a later chapter in this book. The probability of an event is the number of ways that event can occur divided by the total number of outcomes possible. Can you use the Fundamental Principle of Counting twice to solve the last part?
In this section, you learned and applied the Fundamental Principle of Counting. This principle allows us to count the number of outcomes (or ways to complete) a process involving multiple sub-processes. Once we know the number of outcomes possible for each sub-process, then we just multiply these values together to obtain the total number of outcomes possible for the overall process. In each of the next two sections, we’ll be formally introduced to a new tool for computing the number of outcomes of a complex process. In the next section, we’ll discover a technique for counting the number of permutations (orderings) of a subset of elements taken from a collection. In the section that follows that one, we’ll see a method for counting the number of ways to select a subset from a larger collection of objects (where the order of selection does not matter). Perhaps more simply put, the next section will expose us to counting arrangements and the section that follows will show us how to count selections. We’ll see you there!
PrevTopNext