3.1 Fundamental counting principle

Fundamental Counting Principle

Core Concept and Applications

The fundamental counting principle gives you a way to calculate the total number of outcomes when you're making several independent choices in sequence. Instead of listing every single possibility, you just multiply.

Here's the idea: if one event can happen in m ways and a second independent event can happen in n ways, then the two events together can happen in $m \times n$ ways. This extends naturally to any number of events. With k events, the total number of outcomes is:

$n_1 \times n_2 \times n_3 \times \ldots \times n_k$

where $n_i$ is the number of options for the i-th event.

A few things to keep in mind:

• The events must be independent, meaning one choice doesn't affect the options available for another
• The principle counts ordered outcomes, so choosing shirt-then-pants is treated as a sequence of decisions (this distinguishes it from combinations, which you'll see later)
• It's also called the multiplication principle of counting
• It forms the foundation for more advanced counting techniques like permutations and combinations

Quick example: Choosing an outfit from 3 shirts, 2 pants, and 2 pairs of shoes gives you $3 \times 2 \times 2 = 12$ possible outfits. You don't need to list all 12; the multiplication handles it.

Bigger example: A license plate format uses 3 letters followed by 4 digits. Each letter has 26 options and each digit has 10, so the total is $26 \times 26 \times 26 \times 10 \times 10 \times 10 \times 10 = 175{,}760{,}000$ possible plates. Trying to list those out would be impossible, which is exactly why this principle matters.

Applying the Fundamental Counting Principle

Problem-Solving Steps

When you encounter a counting problem, follow this process:

1. Break the scenario into separate choices or stages. Identify each independent decision that contributes to the final outcome.
2. Count the options at each stage. How many ways can each individual choice be made? Pay attention to whether repetition is allowed (like reusing a letter in a password) or not (like dealing cards from a deck).
3. Multiply all the stage counts together. The product gives you the total number of outcomes.
4. Use exponents when a choice repeats. If the same type of decision happens multiple times with the same number of options each time, you can write it as a power. For instance, flipping a coin 5 times gives $2^5$ rather than writing $2 \times 2 \times 2 \times 2 \times 2$.
5. Sanity-check your answer. Does the result seem reasonable? If you're choosing from a small set of options, a result in the millions should make you double-check your setup.

Practical Examples and Calculations

Meal combinations: A restaurant offers 4 appetizers, 6 main courses, and 3 desserts. You pick one from each category.

$4 \times 6 \times 3 = 72$ possible meals.

Passwords: A password has 3 lowercase letters followed by 2 digits. Letters and digits can repeat.

$26 \times 26 \times 26 \times 10 \times 10 = 1{,}757{,}600$ possible passwords.

Coin flips: A coin is flipped 5 times. Each flip has 2 outcomes (heads or tails), and the same 2 options apply every time.

$2^5 = 32$ possible outcomes. This is a great case for using exponents since the choice repeats identically.

Recognizing When to Use the Fundamental Counting Principle

Identifying Suitable Scenarios

Not every counting problem uses this principle, so you need to recognize the right situations. Look for these clues:

• The problem involves a sequence of independent choices, each with a definite number of options
• The order of choices matters (choosing pizza then salad is a different meal plan than salad then pizza)
• The scenario can be broken into distinct stages, and each stage's options don't depend on what you chose at other stages
• The total number of outcomes is too large to list by hand, so you need a systematic method

One important distinction: if the problem asks "how many ways can you select items where order doesn't matter," that's a combinations problem, not a direct application of the counting principle. You'll learn the difference in upcoming sections on permutations and combinations.

Real-World Applications

Dice rolling: Rolling three six-sided dice produces $6 \times 6 \times 6 = 216$ possible outcomes. Each die is independent with 6 options, so this is $6^3$.

Binary strings: A binary string of length 8 has 2 choices (0 or 1) at each position, giving $2^8 = 256$ possible strings. This same logic applies to any yes/no scenario repeated multiple times.

Bank PINs: A four-digit PIN allows digits 0 through 9 at each position, so there are $10^4 = 10{,}000$ possible PINs. (This is why four-digit PINs aren't considered very secure.)

Delivery routes: A driver needs to visit 5 locations and can choose any order. For the first stop there are 5 choices, then 4 remain, then 3, then 2, then 1. That gives $5 \times 4 \times 3 \times 2 \times 1 = 5! = 120$ possible routes. Notice that here the number of options decreases at each stage because locations can't be revisited. The counting principle still applies; the choices just aren't all the same size.