Fundamental Counting Principles

Why This Matters

Counting principles are the foundation of everything you'll encounter in algebraic 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 ultimately relying on these core principles. The exam will test whether you understand when to apply each principle: 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 to a given scenario and understanding how these principles combine in sophisticated arguments. Master the "why" behind each technique, and you'll be equipped to tackle novel problems rather than just rehearsed examples.

---

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, you need inclusion-exclusion instead

Multiplication Principle

• Use when events are independent and sequential—each choice is made regardless of previous choices
• Formula: If event A occurs in $m$ ways and event B occurs in $n$ ways, then A and B occur in $m \times n$ ways
• Extends to multiple stages—for $k$ independent events with $n_1, n_2, \ldots, n_k$ options, total outcomes equal $n_1 \times n_2 \times \cdots \times n_k$

---

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
• Two-set formula: $|A \cup B| = |A| + |B| - |A \cap B|$; generalizes to $n$ sets with alternating signs
• Essential for "at least one" problems—count elements satisfying at least one property by tracking overlaps systematically

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 yield to this approach

---

Arrangements and Selections

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

Permutations

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

Combinations

• Order doesn't matter—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

---

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 elements of set A with elements of set B perfectly, then $|A| = |B|$
• Transforms hard counts into easy ones—find a bijection to a set you already know how to count
• Fundamental in combinatorial proofs—many identities are proved by showing two expressions count the same set via different bijections

Pigeonhole Principle

• Guarantees duplication—if $n$ items go into $m$ containers with $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—shows something must happen even when you can't identify which specific case

Principle of Mathematical Induction

• Proves statements for all natural numbers—establish a base case, then show "if true for $n$, then true for $n+1$"
• Strong induction variant assumes truth for all values up to $n$, useful for recursive structures
• Essential for combinatorial identities—validates 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$
• Coefficients are combinations—$\binom{n}{k}$ counts ways to choose which $k$ factors contribute $b$ (and which $n-k$ contribute $a$)
• Generates identities—substituting specific values (like $a = b = 1$ or $a = 1, b = -1$) yields useful summation formulas

---

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. Compare permutations and combinations: if $P(5,3) = 60$ and $\binom{5}{3} = 10$, explain the factor of 6 difference in terms of what each formula counts.

4. An FRQ states: "Prove that 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.