Counting Principles

Before you can calculate a probability, you need to know how many outcomes are possible. Counting principles give you systematic methods to count outcomes without listing every one. These techniques underpin probability, statistics, and discrete mathematics. In this lesson you will learn the fundamental counting principle (multiplication rule), the addition principle, tree diagrams, and how to handle restrictions and overcounting.

The Fundamental Counting Principle

The fundamental counting principle (also called the multiplication principle) states:

If one event can occur in $m$ ways and a second independent event can occur in $n$ ways, then both events together can occur in $m \times n$ ways.

This extends naturally. If you have a sequence of events with $n_1, n_2, \ldots, n_k$ possible outcomes:

$\text{Total outcomes} = n_1 \times n_2 \times \cdots \times n_k$

Example 1: Restaurant Menu

A restaurant offers 4 appetizers, 6 entrees, and 3 desserts. How many different three-course meals are possible?

$4 \times 6 \times 3 = 72 \text{ meals}$

Example 2: License Plates

A state issues license plates with 3 letters followed by 4 digits. How many different plates are possible?

$26 \times 26 \times 26 \times 10 \times 10 \times 10 \times 10 = 26^3 \times 10^4 = 17{,}576 \times 10{,}000 = 175{,}760{,}000$

Example 3: True/False Test

A quiz has 10 true/false questions. How many ways can a student answer all questions?

$2^{10} = 1{,}024$

Each question has 2 choices, and the choices are independent.

Tree Diagrams

A tree diagram is a visual tool for listing all possible outcomes of a sequence of events. Each branch represents a choice, and the total outcomes are the number of paths from root to leaf.

Example: Flipping a Coin Twice

Event 1: Heads or Tails (2 branches). Event 2: Heads or Tails (2 branches from each).

Outcomes: HH, HT, TH, TT — a total of $2 \times 2 = 4$.

Tree diagrams are most useful for small problems or when probabilities differ across branches. For large problems, the counting principle is faster than drawing the full tree.

Example: Choosing an Outfit

You have 3 shirts (Red, Blue, Green) and 2 pants (Khaki, Black). The tree starts with 3 branches for shirts, each splitting into 2 for pants:

Total outfits: $3 \times 2 = 6$ (RK, RB, BK, BB, GK, GB).

The Addition Principle

The addition principle applies when outcomes come from mutually exclusive categories (no overlap):

If event $A$ can occur in $m$ ways and event $B$ can occur in $n$ ways, and $A$ and $B$ cannot both happen, then $A$ or $B$ can occur in $m + n$ ways.

Example: Choosing a Class Representative

A class with 15 boys and 12 girls needs to choose one representative. If the representative is either a boy or a girl (not both):

$15 + 12 = 27 \text{ possible choices}$

Multiplication vs. Addition: When to Use Which

• AND (doing one thing AND then another) → Multiply
• OR (doing one thing OR another, but not both) → Add

A combo meal offers a burger OR a sandwich (5 choices total) AND a drink (3 choices): $5 \times 3 = 15$ meals. You add the burger and sandwich counts within their category and multiply across categories.

Factorial Notation

The factorial of a positive integer $n$ is the product of all positive integers up to $n$:

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

Important values:

Why does $0! = 1$? By convention and for consistency: $n! = n \times (n-1)!$ requires $1! = 1 \times 0!$, so $0! = 1$.

Counting Arrangements with Factorials

How many ways can 5 books be arranged on a shelf?

The first position has 5 choices, the second has 4, and so on:

$5 \times 4 \times 3 \times 2 \times 1 = 5! = 120$

Counting with Restrictions

Real counting problems often have constraints. The strategy is to count what is allowed directly or use the complement (total minus forbidden).

Example: No Repetition Allowed

How many 3-letter “words” can be formed from the letters A, B, C, D, E if no letter is repeated?

$5 \times 4 \times 3 = 60$

The first position has 5 choices. After using one letter, the second has 4. After two letters are used, the third has 3.

Example: Digits with a Restriction

How many 4-digit numbers (1000 to 9999) have no repeated digits?

• First digit: 9 choices (1 through 9 — cannot be 0)
• Second digit: 9 choices (0 through 9 minus the first digit)
• Third digit: 8 choices
• Fourth digit: 7 choices

$9 \times 9 \times 8 \times 7 = 4{,}536$

Example: Complement Method

How many 3-letter “words” from A through Z contain at least one vowel (A, E, I, O, U)?

Direct counting would require cases (exactly 1 vowel, exactly 2, all 3). The complement is easier.

Total 3-letter words: $26^3 = 17{,}576$

Words with no vowels (only 21 consonants): $21^3 = 9{,}261$

Words with at least one vowel: $17{,}576 - 9{,}261 = 8{,}315$

Overcounting

Overcounting occurs when different counting paths lead to the same outcome. This is a key idea that motivates combinations.

Example: Choosing a Committee

How many ways can you choose 2 people from Alice, Bob, and Carol for a committee?

If you list ordered pairs: (Alice, Bob), (Bob, Alice), (Alice, Carol), (Carol, Alice), (Bob, Carol), (Carol, Bob) — that is $3 \times 2 = 6$.

But (Alice, Bob) and (Bob, Alice) are the same committee. Every committee was counted twice (once for each order). Correct count:

$\frac{6}{2} = 3 \text{ committees: } \{A,B\}, \{A,C\}, \{B,C\}$

Dividing by the number of rearrangements is exactly what combinations do. You will formalize this in the next lesson.

Real-World Application: Retail Inventory

A clothing store sells T-shirts that come in 5 sizes (XS, S, M, L, XL), 8 colors, and 3 styles (crew neck, V-neck, henley). The store wants to stock one of each combination.

$5 \times 8 \times 3 = 120 \text{ distinct SKUs}$

If the store adds a 4th style, the inventory jumps to $5 \times 8 \times 4 = 160$ — a 33 percent increase from one additional style option. The counting principle helps businesses forecast inventory needs.

Common Mistakes

1. Adding when you should multiply (and vice versa). “AND” → multiply. “OR” → add.
2. Forgetting restrictions on the first position. When forming numbers, the leading digit usually cannot be 0.
3. Double-counting. When counting committees, teams, or sets, order does not matter — divide out the duplicates.
4. Confusing “with repetition” and “without repetition.” A lock code 1-1-1 allows repetition; a committee with distinct members does not.

Practice Problems

Key Takeaways

• The fundamental counting principle multiplies the number of choices across sequential independent events
• The addition principle adds the number of choices across mutually exclusive categories
• Tree diagrams visualize outcomes for small, sequential problems
• Factorials ($n!$) count the number of ways to arrange $n$ distinct objects in order
• For problems with restrictions, either count directly with the constraint or use the complement (total minus forbidden)
• Overcounting happens when different orderings produce the same outcome — divide by the number of rearrangements

Return to College Algebra for more topics in this section.