Addition Principle

Math for CS · Axiom Academy

Counting disjoint choices -- the sum rule in action The addition principle (sum rule) is the simplest counting tool: when you have mutually exclusive options, you add the counts. In plain English: if you can do task 1 in m ways OR task 2 in n ways, and you can't do both simultaneously, then there are m + n total ways. The critical word is disjoint . The sum rule only works when the sets don't overlap. The most powerful use of the addition principle is case analysis : split a hard counting problem into disjoint cases, count each case separately, then add. Direct approach is hard. Instead, use complementary counting: Total 3-digit numbers: 900 (from 100 to 999) 3-digit numbers with NO digit equal to 5: first digit has 8 choices (1-9 except 5), other digits have 9 choices each (0-9 except 5) = 8 9 9 = 648 Case A (start with 01): 2^4 = 16 strings Case B (end with 10): 2^4 = 16 strings Overlap (start with 01 AND end with 10): 2^2 = 4 strings When sets are NOT disjoint, we need a correction: This is the beginning of the inclusion-exclusion principle , which generalizes to any number of sets. For now, the key insight: the basic sum rule is the special case where |A B| = 0 .

This is the written version of the interactive lesson above. See the full Math for CS course.