Permutations, Combinations, and Identities
Pillar: Set — "\(\binom{n}{k}\) counts the subsets of size \(k\) from a set of \(n\) elements. Every identity is a statement about sets — symmetry, splitting, combining."
The Setup
You're on LC 62 — Unique Paths. A robot sits at the top-left of an \(m \times n\) grid and needs to reach the bottom-right, moving only right or down. For a \(3 \times 7\) grid, the answer is \(28\).
Where does \(28\) come from? The robot makes exactly \(2\) down-moves and \(6\) right-moves — \(8\) moves total. The question is: in how many ways can you choose which \(2\) of the \(8\) moves are the down-moves? That's \(\binom{8}{2} = 28\).
One problem, zero recursion, zero DP. Just a count of subsets. This is the power of combinatorics: translating a structural question into a counting formula.
But \(\binom{n}{k}\) is only the beginning. The identities that connect binomial coefficients to each other are what make hard problems fall apart. This lesson builds the machinery from the ground up: factorials, permutations, combinations, Pascal's triangle, and seven identities that show up constantly in competitive programming.
Factorials
The factorial of a non-negative integer \(n\), written \(n!\), is the product of all positive integers up to \(n\):
with the convention \(0! = 1\).
Trace \(5!\) by hand: \(1 \times 2 = 2\), \(\times 3 = 6\), \(\times 4 = 24\), \(\times 5 = 120\). So \(5! = 120\).
What does \(n!\) count? It counts the number of ways to arrange \(n\) distinct items in a line. For \(3\) items \(\{A, B, C\}\): \(ABC, ACB, BAC, BCA, CAB, CBA\) — that's \(3! = 6\) arrangements.
Why? There are \(3\) choices for the first position, then \(2\) for the second, then \(1\) for the last. Multiply: \(3 \times 2 \times 1 = 6\).
Permutations
A permutation is an ordered selection. You pick \(k\) items from \(n\) and care about the order.
The logic: \(n\) choices for the first pick, \(n-1\) for the second, down to \(n-k+1\) for the \(k\)-th. That's \(n \times (n-1) \times \cdots \times (n-k+1)\), which equals \(n! / (n-k)!\).
Example: how many 3-letter arrangements from the letters \(\{A, B, C, D, E\}\)?
You can verify: \(5 \times 4 \times 3 = 60\).
Combinations
A combination is an unordered selection. You pick \(k\) items from \(n\) and don't care about the order.
The derivation is clean. Start with \(P(n, k) = n!/(n-k)!\) ordered selections. Each group of \(k\) items appears in \(k!\) different orders. Since you don't care about order, divide by \(k!\):
Example: how many ways to choose \(3\) items from \(\{A, B, C, D, E\}\)?
The \(60\) permutations collapse into \(10\) combinations because each group of \(3\) has \(3! = 6\) orderings.
Return to the grid problem: the robot makes \(m - 1\) down-moves and \(n - 1\) right-moves, for a total of \(m + n - 2\) moves. Choose which \(m - 1\) of them are down-moves:
For \(m = 3\), \(n = 7\): \(\binom{8}{2} = 28\). Done.
Pascal's Triangle
Build \(\binom{n}{k}\) for small \(n\) without any division. Pascal's triangle gives you a recurrence:
with base cases \(\binom{n}{0} = \binom{n}{n} = 1\).
Combinatorial proof. You have \(n\) elements and need to choose \(k\). Focus on element \(n\). Either it's in the subset or it's not:
- Element \(n\) is in: choose the remaining \(k-1\) from the first \(n-1\) elements. That's \(\binom{n-1}{k-1}\) ways.
- Element \(n\) is out: choose all \(k\) from the first \(n-1\) elements. That's \(\binom{n-1}{k}\) ways.
These two cases are disjoint and exhaustive. Sum them.
The first several rows of Pascal's triangle:
Every entry is the sum of the two entries directly above it. This is the DP table for combinations, and it's often the cleanest way to compute \(\binom{n}{k}\) when \(n\) is small (say, \(n \leq 5000\)) and you don't want to deal with modular inverses.
Key Identities
These seven identities appear over and over. Each one has a short combinatorial proof — a story about sets that makes the algebra obvious.
1. Symmetry
Proof. Choosing which \(k\) elements to include is the same as choosing which \(n-k\) elements to exclude. Every subset of size \(k\) corresponds to exactly one complement of size \(n-k\).
This is the identity that tells you \(\binom{100}{97} = \binom{100}{3} = 161700\). Always reduce to the smaller side.
2. Row Sum
Proof. The left side counts all subsets of an \(n\)-element set (subsets of size \(0\) + subsets of size \(1\) + \(\cdots\) + subsets of size \(n\)). The right side counts the same thing: each of the \(n\) elements is independently in or out, giving \(2^n\) total subsets.
3. Weighted Sum
Proof. The left side counts the total number of (element, subset containing that element) pairs across all subsets. Count the other way: pick a "leader" from the \(n\) elements (\(n\) choices), then form any subset of the remaining \(n-1\) elements (\(2^{n-1}\) choices). The leader is automatically in the subset.
4. Alternating Sum
Proof. The number of even-sized subsets equals the number of odd-sized subsets. To see this, fix one element \(x\). Every subset not containing \(x\) pairs with the subset that does contain \(x\). This is a parity-toggling bijection. (For \(n = 0\), the sum is \(1\), not \(0\).)
Alternatively, plug \(x = -1\) into the binomial theorem: \((1 + (-1))^n = 0\).
5. Hockey Stick (Prefix Column Sum)
Proof. You want to choose \(k + 1\) elements from \(\{1, 2, \ldots, n+1\}\). Condition on the largest element chosen. If the largest is \(i + 1\) (where \(k \leq i \leq n\)), then the remaining \(k\) elements come from \(\{1, \ldots, i\}\), giving \(\binom{i}{k}\) ways. Sum over all possible largest elements.
The name comes from the shape on Pascal's triangle: a vertical run of entries plus one diagonal step sums to the entry at the corner — like a hockey stick.
Example: \(\binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} = 1 + 3 + 6 + 10 = 20 = \binom{6}{3}\).
6. Vandermonde's Identity
Proof. You have two groups: \(m\) red elements and \(n\) blue elements, \(m + n\) total. Choose \(r\) from the combined group: \(\binom{m+n}{r}\) ways. Alternatively, decide how many come from each group: \(j\) from red and \(r - j\) from blue, for each valid \(j\). Sum over \(j\).
This generalizes symmetry (\(m = n\), specific \(r\)) and connects to many advanced identities.
7. Square Sum (Vandermonde Special Case)
Proof. Set \(m = n\) and \(r = n\) in Vandermonde:
By symmetry, \(\binom{n}{n-j} = \binom{n}{j}\), so the left side becomes \(\sum \binom{n}{j}^2\).
Concretely: choose \(n\) items from \(2n\) by splitting them into two groups of \(n\) — pick \(k\) from the first group and \(n - k\) from the second.
Identities Reference Table
| Identity | Formula | One-Line Proof |
|---|---|---|
| Symmetry | \(\binom{n}{k} = \binom{n}{n-k}\) | Include \(k\) = exclude \(n-k\) |
| Row sum | \(\sum \binom{n}{k} = 2^n\) | Each element in or out |
| Weighted sum | \(\sum k\binom{n}{k} = n \cdot 2^{n-1}\) | Pick a leader, subset the rest |
| Alternating sum | \(\sum (-1)^k\binom{n}{k} = 0\) | Bijection toggles parity; equal even/odd subsets |
| Hockey stick | \(\sum_{i=k}^{n}\binom{i}{k} = \binom{n+1}{k+1}\) | Condition on the largest chosen element |
| Vandermonde | \(\sum_{j}\binom{m}{j}\binom{n}{r-j} = \binom{m+n}{r}\) | Choose \(r\) from two groups of sizes \(m\) and \(n\) |
| Square sum | \(\sum \binom{n}{k}^2 = \binom{2n}{n}\) | Vandermonde with \(m = n\), \(r = n\) |
The Code
Pascal's Triangle DP
When \(n \leq 5000\) or so, build the triangle directly. No modular inverse needed — just addition.
vector<vector<long long>> buildPascalTriangle(int maxN) {
vector<vector<long long>> pascal(maxN + 1, vector<long long>(maxN + 1, 0));
for (int row = 0; row <= maxN; row++) {
pascal[row][0] = 1;
for (int col = 1; col <= row; col++) {
pascal[row][col] = pascal[row - 1][col - 1] + pascal[row - 1][col];
}
}
return pascal;
}
\(O(n^2)\) time, \(O(n^2)\) space.
If you need results modulo a prime, add % mod inside the inner loop. If you only need one row at a time, keep two rows and alternate — drops space to \(O(n)\).
Factorial Computation with Mod
For large \(n\) (up to \(2 \times 10^5\) or more), precompute factorials and their modular inverses. Then \(\binom{n}{k} = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \bmod p\) in \(O(1)\) per query.
Using the modpow function from Ch4 L2:
const long long MOD = 1e9 + 7;
long long modpow(long long base, long long exponent, long long mod) {
long long result = 1;
base %= mod;
while (exponent > 0) {
if (exponent & 1) result = result * base % mod;
base = base * base % mod;
exponent >>= 1;
}
return result;
}
vector<long long> precomputeFactorials(int maxN, long long mod) {
vector<long long> factorial(maxN + 1);
factorial[0] = 1;
for (int i = 1; i <= maxN; i++) {
factorial[i] = factorial[i - 1] * i % mod;
}
return factorial;
}
vector<long long> precomputeInverseFactorials(int maxN, long long mod) {
auto factorial = precomputeFactorials(maxN, mod);
vector<long long> inverseFactorial(maxN + 1);
inverseFactorial[maxN] = modpow(factorial[maxN], mod - 2, mod);
for (int i = maxN - 1; i >= 0; i--) {
inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod;
}
return inverseFactorial;
}
long long nCr(int n, int k, const vector<long long>& factorial,
const vector<long long>& inverseFactorial, long long mod) {
if (k < 0 || k > n) return 0;
return factorial[n] % mod * inverseFactorial[k] % mod * inverseFactorial[n - k] % mod;
}
\(O(n)\) precomputation, \(O(1)\) per query.
The trick for inverse factorials: compute only \((maxN!)^{-1}\) using Fermat's little theorem (one modpow call), then build downward using \((i!)^{-1} = ((i+1)!)^{-1} \times (i+1)\). This gives you all inverse factorials with a single modular exponentiation instead of \(n\) separate ones.
Common Mistakes
-
Integer overflow in Pascal's triangle. Without
% mod, \(\binom{n}{k}\) overflowslong longfor \(n\) around \(66\) (\(\binom{66}{33} > 2^{63}\)). If you're building Pascal's triangle for moderate \(n\) without a modulus, you need big integers or you need to rethink the approach. -
Off-by-one in factorial precomputation. If your problem has \(n\) up to \(2 \times 10^5\), you need
factorial[200000]. Allocating size \(200000\) instead of \(200001\) gives a buffer overrun. Always allocatemaxN + 1. -
Forgetting the \(k > n\) guard. \(\binom{n}{k}\) is \(0\) when \(k > n\) or \(k < 0\). If your
nCrfunction doesn't check this, you'll index out of bounds or return garbage.
Quick Recap
- \(n!\) counts arrangements of \(n\) items. \(P(n,k) = n!/(n-k)!\) counts ordered selections. \(\binom{n}{k} = n!/(k!(n-k)!)\) counts unordered selections.
- Pascal's recurrence \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) builds the triangle with pure addition — no division, no modular inverse.
- Seven identities (symmetry, row sum, weighted sum, alternating sum, hockey stick, Vandermonde, square sum) each have a one-line combinatorial proof rooted in set counting.
- Two computation methods: Pascal DP (\(O(n^2)\), good for small \(n\)) and factorial precomputation (\(O(n)\) setup, \(O(1)\) query, requires prime mod).
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CSES — Binomial Coefficients | cses.fi/problemset/task/1079 | Easy | Precompute factorials + inverse factorials; \(O(1)\) per query |
| LC 62 — Unique Paths | leetcode.com/problems/unique-paths | Easy | Grid paths = \(\binom{m+n-2}{m-1}\); direct formula or Pascal DP |
| LC 1569 — Number of Ways to Reorder Array to Get Same BST | leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst | Hard | Recursive counting with \(\binom{n}{k}\); Vandermonde-style splitting |