Combination Formulas

Why This Matters

Combination formulas are the backbone of counting problems where order doesn't matter—and that distinction is exactly what you're being tested on. Whether you're calculating probabilities, expanding binomials, or solving distribution problems, these formulas give you the tools to count selections systematically. The key concepts you'll encounter include selection without replacement, selection with repetition, symmetry properties, and algebraic connections that link combinatorics to polynomial expressions.

Don't just memorize the formulas—understand when each one applies and why it works. Exams will test whether you can recognize which formula fits a given scenario, connect identities to Pascal's Triangle, and apply approximations when exact computation isn't feasible. Master the underlying logic, and you'll handle any counting problem thrown your way.

---

Core Selection Formulas

These formulas handle the fundamental question: how many ways can you choose items from a set? The key distinction is whether repetition is allowed.

Basic Combination Formula

• $C(n,r) = \frac{n!}{r!(n-r)!}$—counts selections of $r$ elements from $n$ distinct items where order doesn't matter
• Factorial division eliminates overcounting; dividing by $r!$ removes the $r!$ arrangements of the chosen items
• Use this when each item can only be selected once and you're choosing a subset, not arranging it

Combination with Repetition

• $C(n+r-1, r)$—counts selections when the same item type can be chosen multiple times
• Stars and bars transformation converts the problem into placing $r$ identical objects into $n$ distinct categories
• Classic application: choosing $r$ donuts from $n$ flavors, or distributing identical items among groups

Multiset Combinations

• $C(n+k-1, k)$—equivalent to combination with repetition; selects $k$ elements from $n$ types allowing repeats
• Partition problems frequently use this formula when distributing indistinguishable objects
• Key insight: this generalizes basic combinations to scenarios where "sampling with replacement" occurs

---

Symmetry and Simplification Properties

These properties reduce computational effort by exploiting the inherent structure of combinations. Recognizing symmetry can turn a difficult calculation into a trivial one.

Complementary Combination Property

• $C(n,r) = C(n, n-r)$—choosing $r$ items is equivalent to choosing which $n-r$ items to leave out
• Computational shortcut: always use the smaller value; $C(100, 98) = C(100, 2) = 4950$
• Conceptual symmetry reflects that every selection implies a complementary non-selection

Pascal's Triangle Connection

• Each entry equals $C(n,k)$—row $n$, position $k$ gives the combination value directly
• Addition property: $C(n,k) = C(n-1, k-1) + C(n-1, k)$ explains how each entry sums the two above it
• Visual tool for quickly finding small combination values and recognizing patterns in binomial coefficients

---

Algebraic Connections

These results bridge combinatorics and algebra, showing how counting appears in polynomial expansions. The binomial theorem is particularly high-yield for exams.

Binomial Theorem

• $(x + y)^n = \sum_{k=0}^{n} C(n,k) \cdot x^{n-k} \cdot y^k$—expands any binomial power using combination coefficients
• Each coefficient $C(n,k)$ counts the ways to select $k$ factors of $y$ from $n$ total factors
• Direct applications: finding specific terms in expansions, computing sums of combinations, probability calculations

Vandermonde's Identity

• $C(m+n, r) = \sum_{k=0}^{r} C(m,k) \cdot C(n, r-k)$—splits selection across two groups of sizes $m$ and $n$
• Combinatorial proof: choosing $r$ items from a combined group equals summing all ways to split the selection between subgroups
• Problem-solving tool for committee selections from multiple populations or combining independent choices

---

Advanced Identities and Techniques

These tools handle specialized scenarios: summing combinations, working with modular arithmetic, and approximating large values. Know when to apply each one.

Hockey-Stick Identity

• $\sum_{i=0}^{k} C(n+i, i) = C(n+k+1, k)$—sums a diagonal in Pascal's Triangle to produce a single combination
• Visual pattern traces a "hockey stick" shape in the triangle, with the sum appearing at the blade
• Proof strategy often uses this identity to collapse summations in combinatorial arguments

Lucas' Theorem

• Computes $C(n,r) \mod p$ for prime $p$ by breaking $n$ and $r$ into base-$p$ digits
• Formula: $C(n,r) \equiv \prod_{i} C(n_i, r_i) \pmod{p}$ where $n_i, r_i$ are corresponding digits
• Essential for competitive math and number theory problems involving large combinations mod primes

Stirling's Approximation

• $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$—estimates factorials for large $n$
• Enables analysis of combination growth rates without computing exact (astronomically large) values
• Key application: asymptotic bounds in probability, information theory, and algorithm analysis

---

Quick Reference Table

---

Self-Check Questions

1. Which two formulas would you use for problems involving selection where items can be repeated, and what transformation connects them to basic combinations?

2. A problem asks for $C(50, 47)$. Which property lets you simplify this immediately, and what's the equivalent expression?

3. Compare and contrast the binomial theorem and Vandermonde's identity: both involve sums of combination products, so when would you use each one?

4. You need to compute $C(1000, 500) \mod 7$. Which technique applies here, and why would direct computation fail?

5. An FRQ asks you to prove that $C(n,k) = C(n-1, k-1) + C(n-1, k)$. What visual tool demonstrates this, and how would you construct a combinatorial argument?