1.2 The addition principle (Rule of Sum)

The Addition Principle

The Addition Principle (Rule of Sum) tells you how to count outcomes when you're choosing between mutually exclusive options. If you can pick either option A or option B, and there's no overlap between them, you just add the counts together. It's one of the first counting tools you'll use in combinatorics, and nearly every harder technique builds on it.

The Addition Principle

Definition and Requirements

The Addition Principle states: if there are $m$ ways to do one thing and $n$ ways to do another, and these two things cannot happen at the same time (they're mutually exclusive), then there are $m + n$ ways to do one or the other.

In set theory notation, if sets $A$ and $B$ are disjoint (they share no elements):

$|A \cup B| = |A| + |B|$

A few things to keep straight:

• Mutually exclusive means the two events can't both occur. There's zero overlap. If you're picking a card that's either a heart or a spade, those are mutually exclusive because no card is both.
• The principle extends naturally beyond two options. If you have three or more disjoint sets, you just keep adding.
• If the events do overlap, the Addition Principle alone will overcount. You'd need the inclusion-exclusion principle instead, which you'll see later.

Mathematical Foundations

The generalized form for $n$ disjoint sets is:

$|A_1 \cup A_2 \cup \cdots \cup A_n| = |A_1| + |A_2| + \cdots + |A_n|$

This connects directly to partitions: if you split a set into non-overlapping subsets that cover the whole set, the total size equals the sum of the subset sizes. That idea shows up constantly in combinatorics, probability, and computer science (for example, when you analyze how many paths an algorithm can take through branching logic).

The Addition Principle also serves as a building block for permutations and combinations, which you'll encounter soon.

Applying the Addition Principle

Problem-Solving Steps

1. Identify the distinct options or categories. What are the separate groups you're choosing between?
2. Verify mutual exclusivity. Ask yourself: can any outcome belong to more than one group? If yes, you can't simply add.
3. Count the outcomes in each group individually.
4. Add the counts together to get the total.

Here's a concrete example:

For more complex problems, you'll often combine the Addition Principle with the Multiplication Principle. The Addition Principle handles "or" situations; the Multiplication Principle handles "and" situations. Recognizing which one applies is half the battle.

Common Applications

• Games of chance: A standard die can land on an even face (3 outcomes) or an odd face (3 outcomes). Total outcomes: $3 + 3 = 6$.
• Transportation routes: If there are 2 bus routes and 3 train routes between two cities, and you'll take exactly one, that's $2 + 3 = 5$ options.
• Course selection: A student choosing one elective from 5 science courses or 4 humanities courses has $5 + 4 = 9$ options, assuming no course is listed in both departments.
• Programming logic: Counting distinct execution paths through an if/else branch means adding the paths in each branch.

The Addition Principle in Real-World Scenarios

Identifying Applicable Situations

The key signal is an "either-or" choice where only one option gets selected. Watch for these patterns:

• You're choosing from separate, non-overlapping categories (picking an appetizer or a dessert, not both).
• An item belongs to exactly one classification (a student is in the biology department or the chemistry department, not both).
• A probability question asks for $P(A \text{ or } B)$ where $A$ and $B$ can't both happen.

The moment you suspect overlap between categories, pause. If a student could be double-majoring in both biology and chemistry, straight addition would overcount that student.

Practical Examples

• Restaurant menu: A prix fixe menu lets you pick one starter from 6 appetizers or one from 4 soups. That's $6 + 4 = 10$ starter options.
• Travel planning: Flying offers 3 options, taking a train offers 2, and driving offers 1. Total ways to make the trip: $3 + 2 + 1 = 6$.
• Academic programs: A university has 12 BA programs and 8 BS programs with no overlap. A student choosing one major has $12 + 8 = 20$ options.
• Genetics: If a gene has 3 possible dominant genotypes and 1 possible recessive genotype (mutually exclusive categories), total possible genotypes for that gene: $3 + 1 = 4$.

In each case, the logic is the same: confirm no overlap, then add.