Rule of sum

Intuitively, the rule of sum states that the number of ways to do something plus the number of ways to do another thing is the total number of ways to do either. In mathematical terms:

The cardinality of the union of finite sets \(A_1, ... A_n\), such that none of the sets share elements in common (they are pairwise disjoint) is the sum of their individual cardinalities: $$|A_1 \cup ... \cup A_n| = |A_1| + ... + |A_n|$$
⚠ In keeping with the whole "number of ways to do a thing" metaphor, imagine each set above as the set of all the different ways to do its associated "thing."

It should be clear that \(A_1 \cup ... \cup A_n\) is the set that contains all the elements of \(A_1, ... A_n.\) Since these sets are pairwise disjoint, we don't need to worry about accidentally counting an element twice, so \(|A_1 \cup ... \cup A_n|\) is exactly equal to the sum of the number of elements in each set.

As an example, suppose that your choices for dessert tonight can be split up into two categories, being: pies \(\set{\text{pumpkin pie}, \text{cherry pie}, \text{shoo-fly pie}}\) and cakes \(\set{\text{chocolate cake}, \text{cheesecake}}.\) Among these desserts, you can only choose \(1.\) How many choices do you have? The rule of sum says you have exactly \(3 + 2 = 5\) choices of dessert. One such choice would be \(\text{cheesecake}.\) Notice that you are not choosing one from each category, but instead one out of all the categories combined. This is what distinguishes when you want to use the rule of sum versus the rule of product.

Imagine that a case-insensitive password is defined as a string of \(10\) to \(12\) alphanumeric characters, meaning that there are \(26 + 10 = 36\) choices for each character by the rule of sum. How many unique passwords exist? Well, applying the rule of product tells us that the number of unique passwords of length \(10\) would be \(36^{10}.\) With similar logic, we can find that there are \(36^{11}\) unique \(11\)-character passwords and \(36^{12}\) unique \(12\)-character passwords. Finally, by the rule of sum, there are \(36^{10} + 36^{11} + 36^{12}\) unique passwords to choose from. One such password would be \(\text{cheesecake}.\) Haha, \(\text{cheesecake}\) worked for both examples.

Let's move onto an example with binary strings. How many binary strings of length \(4\) or \(5\) exist that start with a \(0\)? Well, if the first character must be restricted to \(0\), we have only \(1\) option for it, being \(0.\) That means the rule of product would determine that there are \(1 * 2 * 2 * 2 = 8\) binary strings of length \(4\) that start with \(0\), and \(1 * 2 * 2 * 2 * 2 = 16\) binary strings of length \(5\) that start with \(0.\) Since a binary string cannot have both length \(4\) and \(5\), the set of binary strings of length \(4\) that start with \(0\) is disjoint from the set of binary strings of length \(5\) that start with \(0\), allowing us to use the sum rule to find that there are \(8 + 16 = 24\) binary strings of length \(4\) or \(5\) that start with a \(0.\)

⚠ Observe that when one of the characters in a binary string of length \(n\) is restricted, there become \(2^{n-1}\) options for it, the same as the number of binary strings of length \(n-1.\) It should make sense that restricting \(1\) character has the same effect as reducing the length by \(1\), because both cause you to lose exactly \(1\) choice of character.
Logic & Proofs
Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form
Set Theory
Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof
Functions
Function • Floor function • Ceiling function • Inverse function
Algorithms
Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm
Relations
Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class
Number Theory
Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm
Induction
Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition
Combinatorics
Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle
Graph Theory
Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm
Recursion
Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort