Combination Formulas

Why This Matters

Combination formulas are the backbone of counting problems where order doesn't matter. Whether you're calculating probabilities, expanding binomials, or solving distribution problems, these formulas let you count selections systematically. The key concepts 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. You'll be tested on recognizing which formula fits a given scenario, connecting identities to Pascal's Triangle, and applying approximations when exact computation isn't feasible.

---

Core Selection Formulas

These formulas answer 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)!}$

This counts the number of ways to select $r$ elements from $n$ distinct items when order doesn't matter. The division by $r!$ is what separates combinations from permutations: it removes the $r!$ different arrangements of the same chosen subset, so you only count each group of items once.

Use this when each item can only be selected once and you care about which items are chosen, not the order you pick them in.

For example, choosing 3 people from a group of 10 for a committee: $C(10,3) = \frac{10!}{3! \cdot 7!} = 120$.

Combination with Repetition (Stars and Bars)

$C(n+r-1, r)$

This counts selections when the same item type can be chosen multiple times. The stars and bars method converts the problem into placing $r$ identical objects (stars) into $n$ distinct categories, separated by $n-1$ dividers (bars). The total number of symbols is $n+r-1$, and you're choosing where to place the $r$ stars (or equivalently, the $n-1$ bars).

Classic application: choosing $r = 8$ donuts from $n = 4$ flavors gives $C(4+8-1, 8) = C(11, 8) = 165$ possible selections. This also covers distributing identical items among groups, like splitting 20 identical coins among 5 people.

Multiset Combinations

$C(n+k-1, k)$

This is the same formula as combination with repetition, just written with $k$ instead of $r$. You'll see both notations depending on the textbook. It selects $k$ elements from $n$ types, allowing repeats.

Partition problems frequently use this formula when distributing indistinguishable objects into distinguishable bins.

---

Symmetry and Simplification Properties

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

Complementary Combination Property

$C(n,r) = C(n, n-r)$

Choosing $r$ items to include is the same as choosing $n-r$ items to leave out. Every selection defines a complementary non-selection of the remaining items.

This is a huge computational shortcut. Always use the smaller value:

$C(100, 98) = C(100, 2) = \frac{100 \cdot 99}{2} = 4950$

That's two multiplications and one division instead of dealing with $98!$.

Pascal's Triangle Connection

Each entry in Pascal's Triangle equals $C(n,k)$, where $n$ is the row number (starting from 0) and $k$ is the position within that row (also starting from 0).

The addition property (also called Pascal's Rule) explains how the triangle is built:

$C(n,k) = C(n-1, k-1) + C(n-1, k)$

Each entry is the sum of the two entries directly above it. The combinatorial reasoning: when choosing $k$ items from $n$, consider one specific element. Either you include it (and choose $k-1$ more from the remaining $n-1$) or you exclude it (and choose all $k$ from the remaining $n-1$).

Pascal's Triangle is a quick visual tool for finding small combination values and spotting patterns in binomial coefficients.

---

Algebraic Connections

These results bridge combinatorics and algebra, showing how counting appears in polynomial expansions.

Binomial Theorem

$(x + y)^n = \sum_{k=0}^{n} C(n,k) \cdot x^{n-k} \cdot y^k$

This expands any binomial power using combination coefficients. Why do combinations show up here? When you multiply out $(x+y)^n$, you're making $n$ independent choices of either $x$ or $y$. The coefficient $C(n,k)$ counts the number of ways to pick $y$ exactly $k$ times out of those $n$ factors.

Direct applications:

• Finding a specific term in an expansion (e.g., the $x^3 y^7$ term in $(x+y)^{10}$ has coefficient $C(10,7) = 120$)
• Computing sums of combinations by substituting specific values of $x$ and $y$ (setting $x = y = 1$ gives $\sum C(n,k) = 2^n$)
• Probability calculations involving binomial distributions

Vandermonde's Identity

$C(m+n, r) = \sum_{k=0}^{r} C(m,k) \cdot C(n, r-k)$

This splits a selection across two disjoint groups of sizes $m$ and $n$. The combinatorial proof is straightforward: choosing $r$ items from a combined group of $m+n$ people is the same as summing over all ways to take $k$ from the first group and $r-k$ from the second.

Use this for committee selections from multiple populations. For example, choosing 5 members from a department of 8 professors and 12 students: $C(20,5) = \sum_{k=0}^{5} C(8,k) \cdot C(12, 5-k)$.

---

Advanced Identities and Techniques

These tools handle specialized scenarios: summing combinations, working with modular arithmetic, and approximating large values.

Hockey-Stick Identity

$\sum_{i=0}^{k} C(n+i, i) = C(n+k+1, k)$

An equivalent form you'll also see: $\sum_{i=r}^{n} C(i, r) = C(n+1, r+1)$. Both collapse a sum of combinations along a diagonal of Pascal's Triangle into a single combination value. The name comes from the visual pattern: the summed entries trace a diagonal line, and the result sits at the "blade" of the hockey stick, one row below and one position over.

This identity is useful for simplifying summations in combinatorial proofs and competition problems.

Lucas' Theorem

For a prime $p$, Lucas' Theorem computes $C(n,r) \mod p$ by breaking $n$ and $r$ into their base-$p$ digit representations:

$C(n,r) \equiv \prod_{i} C(n_i, r_i) \pmod{p}$

where $n_i$ and $r_i$ are the corresponding digits of $n$ and $r$ in base $p$. Each factor $C(n_i, r_i)$ involves numbers smaller than $p$, making the computation manageable. If any $r_i > n_i$, the entire product is 0 mod $p$.

Essential for competitive math and number theory problems involving large combinations mod primes, where direct computation of factorials is impossible.

Stirling's Approximation

$n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$

This estimates factorials for large $n$ without computing exact (astronomically large) values. The approximation becomes increasingly accurate as $n$ grows.

Key applications: asymptotic bounds in probability, information theory, and algorithm analysis. For instance, you can use Stirling's approximation to show that $C(2n, n) \approx \frac{4^n}{\sqrt{\pi n}}$, which reveals the growth rate of central binomial coefficients.

---

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?