Combinations & Pascal's Triangle

June 2026 · 22 min read

If permutations ask "how many ways to arrange?", combinations ask "how many ways to choose?" Removing the ordering constraint from P(n, r) gives us the binomial coefficient C(n, r) — arguably the single most important quantity in combinatorics.

Combinations Defined

A combination is an unordered selection of r objects from n distinct objects. Since order doesn't matter, {A, B, C} and {C, A, B} are the same combination.

Permutation (order matters)
Choose 2 from {A, B, C}:
AB, BA, AC, CA, BC, CB
P(3,2) = 6

Combination (order doesn't matter)
Choose 2 from {A, B, C}:
{A,B}, {A,C}, {B,C}
C(3,2) = 3

Every combination of r objects can be arranged in r! ways. So: C(n, r) = P(n, r) / r!

Notation. C(n, r) is also written as (ⁿ_r), "n choose r", or ⁿCᵣ. In code we'll use C(n, r) or nCr(n, r).

The C(n, r) Formula

C(n, r) = n! / (r! · (n − r)!)

Key properties

Symmetry: C(n, r) = C(n, n − r). Choosing r items to include is the same as choosing (n − r) items to exclude.
Boundary: C(n, 0) = C(n, n) = 1.
Absorption: C(n, r) = (n / r) · C(n − 1, r − 1).

// Basic nCr using precomputed factorials & inverse factorials
long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] % MOD * ifac[r] % MOD * ifac[n - r] % MOD;
}

Beware of negative r or r > n. Always return 0 in those cases. Forgetting this check is a frequent source of wrong answers.

Pascal's Triangle

Pascal's triangle encodes all binomial coefficients. Row n contains C(n, 0), C(n, 1), …, C(n, n). The fundamental recurrence:

C(n, k) = C(n − 1, k − 1) + C(n − 1, k)

Every entry is the sum of the two entries above it. This is Pascal's rule, and it has a beautiful combinatorial proof: to choose k items from n, either include the nth item (then choose k−1 from the remaining n−1) or exclude it (choose k from n−1).

				1
			1		1
		1		2		1
	1		3		3		1
1		4		6		4		1

Highlighted: C(4, 2) = 6 = C(3, 1) + C(3, 2) = 3 + 3

// Build Pascal's triangle up to row N (useful when N ≤ ~5000)
const int N = 5001;
long long C[N][N];

void buildPascal() {
    for (int i = 0; i < N; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
}

When to use Pascal's table vs. factorial precomputation. For n ≤ 5000, a 2D table works well and avoids modular inverses entirely. For n up to 10⁶ or larger, use the factorial + inverse-factorial approach from Post 4.

Key Identities

Mastering these identities lets you simplify sums that appear in contest problems.

Row sum

C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ. This is the total number of subsets of an n-element set. Proof: substitute x = 1 in the binomial theorem (1 + x)ⁿ.

Alternating sum

C(n, 0) − C(n, 1) + C(n, 2) − … = 0 (for n ≥ 1). Substitute x = −1.

Prefix sum of a column (Hockey Stick Identity)

C(r, r) + C(r+1, r) + C(r+2, r) + … + C(n, r) = C(n+1, r+1).

Hockey stick in CP. This identity turns an O(n) sum into O(1). Whenever a problem asks "sum of C(i, k) for i from k to n", use hockey stick.

// Sum C(k,k) + C(k+1,k) + ... + C(n,k) // Naive: O(n) additions sum = 0 for i = k to n: sum += C(i, k) // Hockey stick: O(1) sum = C(n + 1, k + 1)

Proof sketch. Induction on n. Base case C(r, r) = C(r+1, r+1). Inductive step: assume the sum up to C(n−1, r) = C(n, r+1), then adding C(n, r) gives C(n, r+1) + C(n, r) = C(n+1, r+1) by Pascal's rule. ∎

Vandermonde's Identity

For non-negative integers m, n, r:

Σₖ C(m, k) · C(n, r − k) = C(m + n, r)

Combinatorial proof. You have m red balls and n blue balls (m + n total). Choose r balls overall: C(m + n, r) ways. Alternatively, choose k red and (r − k) blue; sum over all valid k.

Applications

Simplifying convolutions of binomial coefficients.
Counting paths that pass through a specific point (split the path into two segments).
Evaluating certain polynomial products.

// Verify Vandermonde numerically: sum C(m,k)*C(n,r-k) = C(m+n,r)
bool verifyVandermonde(int m, int n, int r) {
    long long lhs = 0;
    for (int k = 0; k <= r; k++) {
        lhs = (lhs + nCr(m, k) % MOD * nCr(n, r - k)) % MOD;
    }
    long long rhs = nCr(m + n, r);
    return lhs == rhs;
}

Chu-Vandermonde identity

A useful variant for upper-negation: C(−n, k) = (−1)ᵏ · C(n + k − 1, k). This connects "negative" binomial coefficients to ordinary ones and appears when manipulating generating functions.

Implementation

Here's a complete, contest-ready C++ template combining Pascal's table for small n and factorial-based computation for large n.

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;
const int MAXN = 200005;
long long fac[MAXN], ifac[MAXN];

long long pw(long long b, long long e, long long m = MOD) {
    long long r = 1; b %= m;
    for (; e > 0; e >>= 1) {
        if (e & 1) r = r * b % m;
        b = b * b % m;
    }
    return r;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i-1] * i % MOD;
    ifac[MAXN-1] = pw(fac[MAXN-1], MOD - 2);
    for (int i = MAXN-2; i >= 0; i--) ifac[i] = ifac[i+1] * (i+1) % MOD;
}

long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] % MOD * ifac[r] % MOD * ifac[n-r] % MOD;
}

int main() {
    init();
    int n, r;
    cin >> n >> r;
    cout << C(n, r) << "\n";

    // Hockey stick: C(r,r) + C(r+1,r) + ... + C(n,r) = C(n+1,r+1)
    long long sum = 0;
    for (int i = r; i <= n; i++) sum = (sum + C(i, r)) % MOD;
    assert(sum == C(n + 1, r + 1));

    return 0;
}

Memory note. The 2D Pascal table uses O(N²) memory. For N = 5000 that's ~25 million entries (~200 MB for long long). Use int if MOD fits, or switch to the 1D factorial approach.

Practice Problems

CSES — Distributing Apples. Direct application of stars-and-bars (uses combinations).
Codeforces 1549D — Rows of Seats. Case analysis + counting unordered selections.
Codeforces 1462D — Add to Neighbour and Remove. Though not a pure combinatorics problem, the analysis uses subset-counting ideas.
AtCoder ABC 205 E — White and Black Balls. Grid paths + Ballot/Catalan arguments — combinations in disguise.
Codeforces 1436C — Binary Search. Count arrays where binary search finds a target — uses C(n, r) heavily.
CSES — Christmas Party. Derangement + combination ideas from this module.
AtCoder ABC 234 F — Reordering. Multinomial coefficients over all lengths — direct application of combinations and multinomials.

Up next. In Post 4, we tackle the computational backbone: precomputing binomial coefficients modulo a prime using factorial arrays, Fermat's inverse, and Lucas' theorem for huge n.