Fundamental Counting Principles

Why This Matters

Counting principles are the foundation of everything you'll encounter in combinatorics, from generating functions to partition theory to graph enumeration. When you're asked to count structures, prove identities, or analyze discrete systems, you're relying on these core principles. The central question is always: which principle fits this situation? Is this an "or" situation (addition) or an "and" situation (multiplication)? Are sets overlapping? Does order matter?

Don't just memorize formulas. Know what type of counting problem each principle solves. The real skill is recognizing which principle applies and understanding how principles combine in more complex arguments.

---

Basic Counting Operations

These two principles handle the simplest counting scenarios and form the building blocks for everything else. The key distinction is whether events can occur simultaneously.

Addition Principle

• Use when events are mutually exclusive. If choosing one option rules out the others, you add the counts together.
• Formula: If event A occurs in $m$ ways and event B occurs in $n$ ways (with no overlap), then A or B occurs in $m + n$ ways.
• Watch for disjointness. If events can overlap, simple addition overcounts and you need inclusion-exclusion instead.

For example, if a student can take one of 4 math electives or one of 3 science electives (but not both), there are $4 + 3 = 7$ possible choices.

Multiplication Principle

• Use when choices are made in sequence, where the number of options at each stage doesn't depend on previous choices.
• Formula: If event A occurs in $m$ ways and event B occurs in $n$ ways, then A and B together occur in $m \times n$ ways.
• Extends to multiple stages. For $k$ stages with $n_1, n_2, \ldots, n_k$ options, total outcomes equal $n_1 \times n_2 \times \cdots \times n_k$.

For example, if you choose a shirt from 5 options and then pants from 3 options, there are $5 \times 3 = 15$ outfits.

---

Handling Overlapping Sets

When events aren't mutually exclusive, simple addition overcounts. These principles correct for that overlap or sidestep direct counting entirely.

Inclusion-Exclusion Principle

• Corrects for overcounting in unions. Add individual set sizes, subtract pairwise intersections, add back triple intersections, and so on with alternating signs.
• Two-set formula: $|A \cup B| = |A| + |B| - |A \cap B|$
• General formula for $n$ sets: $\left|\bigcup_{i=1}^{n} A_i\right| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| - \cdots$
• Essential for "at least one" problems. Count elements satisfying at least one property by tracking overlaps systematically.

For example, in a class of 30 students where 18 take French, 15 take Spanish, and 8 take both, the number taking at least one language is $18 + 15 - 8 = 25$.

Complementary Counting

• Count what you don't want, then subtract. Total outcomes minus unwanted outcomes equals desired outcomes.
• Formula: $|\text{desired}| = |\text{total}| - |\text{unwanted}|$
• Best when "not X" is simpler than "X." Problems with restrictions like "at least one" or "no repeated elements" often become much easier with this approach.

For example, to count 4-digit PINs (0000–9999) with at least one even digit: total PINs are $10^4 = 10000$, PINs with all odd digits are $5^4 = 625$, so the answer is $10000 - 625 = 9375$.

---

Arrangements and Selections

The distinction between permutations and combinations appears constantly. The question is always: does order matter?

Permutations

• Order matters. These are arrangements where position is significant.
• Formula: The number of permutations of $n$ distinct objects is $n! = n \times (n-1) \times \cdots \times 1$. For arranging $k$ objects chosen from $n$, use $P(n,k) = \frac{n!}{(n-k)!}$
• Think "arrange" or "sequence." Passwords, rankings, and seating arrangements are permutation problems.

For example, $P(5,3) = \frac{5!}{2!} = 60$ counts the number of ways to arrange 3 people in 5 distinct chairs.

Combinations

• Order doesn't matter. These are selections where only membership counts, not arrangement.
• Formula: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, read as "$n$ choose $k$"
• Think "choose" or "select." Committees, subsets, and handshakes are combination problems.

For example, $\binom{5}{3} = \frac{5!}{3! \cdot 2!} = 10$ counts the number of ways to choose a 3-person committee from 5 people.

---

Proof Techniques and Structural Arguments

These principles help you prove counting results and establish that two sets have the same size without computing either directly.

Bijection Principle

• Equal cardinality via one-to-one correspondence. If you can pair every element of set A with exactly one element of set B (and vice versa), then $|A| = |B|$.
• Transforms hard counts into easy ones. Find a bijection from a set that's hard to count to one you already know how to count.
• Fundamental in combinatorial proofs. Many identities are proved by showing two expressions count the same set through different bijections.

For example, to show that an $n$-element set has $2^n$ subsets, you can build a bijection between subsets and binary strings of length $n$: each bit records whether the corresponding element is included (1) or excluded (0).

Pigeonhole Principle

• Guarantees duplication. If $n$ items go into $m$ containers and $n > m$, at least one container holds more than one item.
• Generalized form: With $n$ items and $m$ containers, some container has at least $\lceil n/m \rceil$ items.
• Proves existence without construction. It shows something must happen even when you can't identify which specific case it occurs in.

For example, in any group of 13 people, at least two share a birth month, because 13 people placed into 12 months forces $\lceil 13/12 \rceil = 2$ in some month.

Principle of Mathematical Induction

Induction proves statements for all natural numbers in two steps:

1. Base case: Verify the statement holds for the smallest value (usually $n = 0$ or $n = 1$).
2. Inductive step: Assume the statement holds for $n$ (the inductive hypothesis), then prove it holds for $n + 1$.

The strong induction variant assumes truth for all values up to $n$, which is useful for recursive structures where the $n+1$ case depends on values earlier than $n$.

Induction is essential for validating formulas involving factorials, binomial coefficients, and recurrence relations.

---

Algebraic Tools

The binomial theorem bridges counting and algebra, connecting combinatorial coefficients to polynomial expansions.

Binomial Theorem

• Expands powers of binomials: $(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$
• The coefficients are combinations. $\binom{n}{k}$ counts the number of ways to choose which $k$ of the $n$ factors contribute $b$ (the remaining $n-k$ contribute $a$). This is why binomial coefficients appear in the expansion.
• Generates identities through substitution. Setting $a = b = 1$ gives $2^n = \sum_{k=0}^{n} \binom{n}{k}$, confirming that the total number of subsets of an $n$-element set is $2^n$. Setting $a = 1, b = -1$ gives $0 = \sum_{k=0}^{n} (-1)^k \binom{n}{k}$, showing that the number of even-sized subsets equals the number of odd-sized subsets.

---

Quick Reference Table

---

Self-Check Questions

1. A problem asks you to count passwords that use at least one digit. Which two principles could you apply, and which is likely simpler?

2. You need to prove that the number of subsets of an $n$-element set equals the number of binary strings of length $n$. Which principle would you use, and how?

3. If $P(5,3) = 60$ and $\binom{5}{3} = 10$, explain the factor of 6 difference in terms of what each formula counts.

4. "In any group of 13 people, at least two share a birth month." Which principle applies, and what are the "items" and "containers"?

5. When would you choose inclusion-exclusion over complementary counting? Give a scenario where each method is the better choice.