Counting Principles

Imagine you are at a sandwich shop. You can choose from 4 types of bread, 5 types of protein, and 3 types of cheese. A friend asks, “How many different sandwiches could you possibly make?” You could try listing them all: wheat with turkey and cheddar, wheat with turkey and swiss, wheat with turkey and provolone, wheat with ham and cheddar… but you quickly realize this is going to take a while.

Or consider passwords. If your password must be exactly 8 characters using only lowercase letters, how many possible passwords exist? Nobody is going to list all of those.

This is where counting principles come in. They give you systematic ways to count possibilities without actually listing every single one. And here is why this matters for probability: to calculate the probability of an event, you need to know how many favorable outcomes there are and how many total outcomes are possible. Often, those numbers are far too large to count by hand. Counting principles are your shortcut.

Core Concepts

Why Counting Matters for Probability

Remember the basic probability formula:

$$P(\text{event}) = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}$$

Both the numerator and denominator require counting. For simple situations, you might be able to list everything. But what about calculating the probability of being dealt a specific poker hand? Or the chance that two people in a room share a birthday? Or the likelihood that a randomly generated password matches yours?

In these situations, the numbers are huge, but they follow predictable patterns. Learning to recognize and use these patterns is what counting principles are all about.

The Multiplication Principle (Fundamental Counting Principle)

This is the most important counting rule, and you probably already use it without realizing it.

The Multiplication Principle: If one task can be done in $m$ ways, and a second task can be done in $n$ ways, then both tasks together can be done in $m \times n$ ways.

This extends to any number of tasks: if you have tasks that can be done in $a$, $b$, $c$, … ways respectively, then all tasks together can be done in $a \times b \times c \times \cdots$ ways.

Let us return to the sandwich shop. You have:

• 4 bread choices
• 5 protein choices
• 3 cheese choices

Total possible sandwiches: $4 \times 5 \times 3 = 60$ sandwiches.

The key insight is that for each bread choice, you have all 5 protein options, and for each bread-protein combination, you have all 3 cheese options. The choices are independent - picking wheat bread does not limit your protein options.

When does the multiplication principle apply? When you are making a sequence of independent choices, and you want to count all possible combinations. Think of it as “AND” situations: you need bread AND protein AND cheese.

Tree Diagrams

A tree diagram is a visual way to see all possible outcomes. Each “branch point” represents a choice, and each path from start to finish represents one complete outcome.

Tree diagrams are excellent for:

• Understanding why the multiplication principle works
• Problems with a small number of total outcomes
• Situations where choices might not be independent

For example, if you flip a coin twice, the tree diagram looks like:

Start
├── Heads (1st flip)
│   ├── Heads (2nd flip) → HH
│   └── Tails (2nd flip) → HT
└── Tails (1st flip)
    ├── Heads (2nd flip) → TH
    └── Tails (2nd flip) → TT

You can see there are 4 possible outcomes: HH, HT, TH, TT. This matches the multiplication principle: $2 \times 2 = 4$.

The Addition Principle

While the multiplication principle handles “AND” situations, the addition principle handles “OR” situations.

The Addition Principle: If events are mutually exclusive (they cannot both happen), you add the counts.

For example, suppose a parking lot has 15 red cars and 20 blue cars, and you want to count how many cars are red or blue. Since a car cannot be both red and blue, you add: $15 + 20 = 35$ cars.

When does the addition principle apply? When outcomes fall into separate, non-overlapping categories and you want to count items in any of those categories.

Be careful: if categories overlap, you cannot simply add. If 10 students play soccer, 8 play basketball, and 3 play both, then students who play soccer or basketball is not $10 + 8 = 18$. You would be counting the 3 who play both twice. The correct count is $10 + 8 - 3 = 15$.

Factorials: $n!$

When you arrange $n$ distinct objects in a line, how many arrangements are possible?

For the first position, you have $n$ choices. For the second position, you have $n-1$ remaining choices. For the third position, $n-2$ choices. And so on, until the last position has only 1 choice.

By the multiplication principle, the total number of arrangements is:

$$n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

This product appears so often in counting that it has its own notation and name:

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

We read $n!$ as “n factorial.”

For example:

• $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
• $4! = 4 \times 3 \times 2 \times 1 = 24$
• $3! = 3 \times 2 \times 1 = 6$
• $2! = 2 \times 1 = 2$
• $1! = 1$
• $0! = 1$ (by definition)

That last one might seem strange. Why is $0! = 1$? Think of it this way: how many ways can you arrange zero objects? There is exactly one way - do nothing. This definition also makes many formulas work out correctly.

Factorials grow extremely fast. By $10!$, you are already at 3,628,800. By $20!$, the number is over 2 quintillion. This is why we need these shortcuts rather than listing everything.

Counting with Restrictions

Many real counting problems have constraints. These restrictions change how you count.

Strategy 1: Count step by step, handling restrictions first.

If certain positions or choices have restrictions, deal with those first, then fill in the remaining choices.

For example: How many 3-letter “words” can you form from A, B, C, D, E if the middle letter must be a vowel?

• Middle position: must be A or E → 2 choices
• First position: any of the remaining 4 letters → 4 choices
• Last position: any of the remaining 3 letters → 3 choices

Total: $2 \times 4 \times 3 = 24$ words.

Notice we counted the restricted position first (the middle letter), then worked around it.

Strategy 2: Complementary counting.

Sometimes it is easier to count what you do NOT want and subtract from the total.

For example: How many 4-digit PINs have at least one repeated digit?

Counting all PINs with at least one repeat directly is complicated. Instead:

• Total PINs: $10 \times 10 \times 10 \times 10 = 10,000$
• PINs with NO repeats: $10 \times 9 \times 8 \times 7 = 5,040$
• PINs with at least one repeat: $10,000 - 5,040 = 4,960$

Overcounting and When to Divide

Sometimes a straightforward count gives you a number that is too big because you have counted some outcomes multiple times.

Common situation: Selecting items where order does not matter.

Suppose you are choosing 2 people from a group of 4 (Alice, Bob, Carol, Dave) to form a committee. Using the multiplication principle:

• First choice: 4 options
• Second choice: 3 options
• Total: $4 \times 3 = 12$

But wait. “Alice then Bob” and “Bob then Alice” give the same committee. You have counted each committee twice.

To fix this, divide by the number of ways to arrange your selection:

$$\frac{4 \times 3}{2!} = \frac{12}{2} = 6$$

The 6 committees are: {Alice, Bob}, {Alice, Carol}, {Alice, Dave}, {Bob, Carol}, {Bob, Dave}, {Carol, Dave}.

General principle: If your counting method produces each outcome $k$ times, divide by $k$ to get the correct count.

This idea leads to combinations, which you will study more deeply in the next lesson. For now, just remember: if order does not matter in your final answer, but your counting method treats order as mattering, you need to divide.

Connecting Counting to Probability Calculations

Now that you have tools to count large numbers efficiently, you can calculate probabilities that would otherwise be impossible.

The pattern is always the same:

1. Count the total number of possible outcomes (the denominator)
2. Count the number of favorable outcomes (the numerator)
3. Divide: $P = \frac{\text{favorable}}{\text{total}}$

Counting principles help with both steps 1 and 2.

Notation and Terminology

Examples

Start
├── Cone
│   ├── Chocolate
│   │   ├── Sprinkles → Cone, Chocolate, Sprinkles
│   │   └── No Sprinkles → Cone, Chocolate, No Sprinkles
│   ├── Vanilla
│   │   ├── Sprinkles → Cone, Vanilla, Sprinkles
│   │   └── No Sprinkles → Cone, Vanilla, No Sprinkles
│   └── Strawberry
│       ├── Sprinkles → Cone, Strawberry, Sprinkles
│       └── No Sprinkles → Cone, Strawberry, No Sprinkles
└── Cup
    ├── Chocolate
    │   ├── Sprinkles → Cup, Chocolate, Sprinkles
    │   └── No Sprinkles → Cup, Chocolate, No Sprinkles
    ├── Vanilla
    │   ├── Sprinkles → Cup, Vanilla, Sprinkles
    │   └── No Sprinkles → Cup, Vanilla, No Sprinkles
    └── Strawberry
        ├── Sprinkles → Cup, Strawberry, Sprinkles
        └── No Sprinkles → Cup, Strawberry, No Sprinkles

Key Properties and Rules

The Multiplication Principle

$$\text{If Task 1 has } m \text{ ways and Task 2 has } n \text{ ways, then both tasks have } m \times n \text{ ways.}$$

This extends to any number of tasks: $$\text{Total ways} = n_1 \times n_2 \times n_3 \times \cdots$$

Use when: Making a sequence of independent choices (AND situations).

The Addition Principle

$$\text{If events A and B are mutually exclusive, then A or B can occur in } m + n \text{ ways.}$$

Use when: Counting items that fall into non-overlapping categories (OR situations).

Warning: If categories overlap, use: $|A \cup B| = |A| + |B| - |A \cap B|$

Factorial Properties

$$n! = n \times (n-1)!$$

$$\frac{n!}{(n-k)!} = n \times (n-1) \times \cdots \times (n-k+1)$$ (this counts arrangements of $k$ items chosen from $n$)

Special values:

• $0! = 1$
• $1! = 1$

Arrangement Formulas

Arrangements of $n$ distinct objects: $n!$

Arrangements of $n$ objects where order does not matter (choosing $k$ items): $$\frac{n!}{k!(n-k)!}$$

Strategy Summary

1. Identify whether it is AND or OR - This determines multiplication vs. addition.
2. Check for restrictions - Handle restricted positions first.
3. Ask: Does order matter? - If not, divide to correct for overcounting.
4. Consider complementary counting - For “at least one” problems, try counting the opposite.
5. Verify with small cases - When unsure, test your formula with small numbers you can count by hand.

Real-World Applications

Password Security

Password strength is directly related to counting principles. A password using:

• Only lowercase letters (26 options per character)
• 8 characters long
• Has $26^8 = 208,827,064,576$ possibilities (about 208 billion)

Add uppercase letters (52 options) and you get $52^8 \approx 53$ trillion possibilities.

Add digits and special characters, and the number explodes further. This is why longer, more varied passwords are more secure - they make the “search space” much larger.

Menu Combinations

Fast food restaurants advertise “millions of combinations” for good reason. If a build-your-own bowl has:

• 4 base options
• 6 protein options
• 10 toppings where you can choose any subset

The counting becomes: $4 \times 6 \times 2^{10} = 24 \times 1024 = 24,576$ combinations. (The $2^{10}$ comes from each topping being either included or not - 2 choices for each of 10 toppings.)

Sports Tournaments

In a single-elimination tournament with 64 teams, how many possible ways can the bracket play out? Each game has 2 possible outcomes, and there are 63 games (each game eliminates one team, and you need to eliminate 63 teams to crown a champion). So there are $2^{63} \approx 9.2 \times 10^{18}$ possible brackets - more than 9 quintillion. This is why no one has ever had a perfect March Madness bracket.

License Plates and Identification

States and countries design license plate formats using counting principles to ensure enough unique identifiers for all vehicles. The format (how many letters, how many digits, what characters are allowed) directly determines capacity. A state expecting 20 million registered vehicles needs a format with at least 20 million possibilities.

Genetics and Biology

DNA sequences use an “alphabet” of 4 bases (A, T, C, G). A sequence of length $n$ has $4^n$ possibilities. For a gene that is 1,000 bases long, that is $4^{1000}$ possible sequences - a number with over 600 digits. This is why genetic diversity is so vast.

Self-Test Problems

Summary

• The Multiplication Principle is the foundation of systematic counting: if you make a sequence of independent choices with $a$, $b$, $c$, … options, the total number of outcomes is $a \times b \times c \times \cdots$

• The Addition Principle applies when counting mutually exclusive categories: if outcomes are in separate groups, add the group sizes.

• Factorials ($n!$) count arrangements of $n$ distinct objects. They grow extremely fast: $10! = 3,628,800$.

• Tree diagrams visually show all possible paths and help verify counting calculations for small problems.

• Handle restrictions first when counting with constraints. Deal with the restricted positions or choices before the unrestricted ones.

• Complementary counting often simplifies “at least one” problems: count what you do NOT want and subtract from the total.

• Divide to correct for overcounting when your method counts outcomes multiple times. If order does not matter but your counting treats it as mattering, divide by the number of ways to arrange your selection.

• Connecting to probability: Counting principles give you both the numerator (favorable outcomes) and denominator (total outcomes) for probability calculations. Without these tools, many probability problems would be impossible to solve.

• Real-world applications range from password security and genetics to sports brackets and license plates. Whenever you ask “how many ways?” counting principles provide the answer.