Combinatorics

The problem

A pizza shop has 12 toppings and lets you pick any 5. The owner asks a simple-sounding marketing question: "How many different 5-topping pizzas can we advertise?" You could try to list them all, but the count runs into the hundreds and you would lose track halfway.

This is the core question of combinatorics: how many ways can something happen, without actually writing every possibility down. Choosing 5 of 12 is written C(12, 5) — "12 choose 5" — and the whole art is computing it quickly and without overflow.

A first attempt

The textbook formula is C(n, r) = n! / (r! · (n − r)!). Translate it directly:

from math import factorial

def choose_naive(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

It is correct, but factorials explode. C(12, 5) only equals 792, yet you first build 12! = 479001600 and divide it back down. For C(100, 50) the factorials have over 150 digits — in fixed-width integers they overflow long before the division rescues you. You are computing enormous numbers just to land on a small one.

The insight

There is a way to build the answer with only additions. Pascal's rule says every "choose" value is the sum of the two above it:

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

The reasoning: to pick r items from n, either you take the last item (then choose r−1 from the remaining n−1) or you skip it (choose r from n−1). Those two disjoint cases cover everything. Stack these up and you get Pascal's triangle, where each entry is a binomial coefficient — no factorials, no division, no overflow until the true answer itself is large.

row 0:            1
row 1:          1   1
row 2:        1   2   1
row 3:      1   3   3   1
row 4:    1   4   6   4   1

How it works

The code

def binomial(n, r):
    if r < 0 or r > n:
        return 0
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
        for j in range(1, i + 1):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    return dp[n][r]

print(binomial(12, 5))  # 792

function binomial(n: number, r: number): number {
  if (r < 0 || r > n) return 0;
  const dp: number[][] = Array.from({ length: n + 1 }, () =>
    new Array(n + 1).fill(0)
  );
  for (let i = 0; i <= n; i++) {
    dp[i][0] = 1;
    for (let j = 1; j <= i; j++) {
      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
  }
  return dp[n][r];
}

console.log(binomial(12, 5)); // 792

static long binomial(int n, int r) {
    if (r < 0 || r > n) return 0;
    long[][] dp = new long[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    return dp[n][r];
}

long long binomial(int n, int r) {
    if (r < 0 || r > n) return 0;
    static long long dp[64][64];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    return dp[n][r];
}

#include <vector>
using namespace std;

long long binomial(int n, int r) {
    if (r < 0 || r > n) return 0;
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    return dp[n][r];
}

Complexity

Building the whole triangle costs O(n²) time and space, but it answers every C(n, r) in that range. If you only need one row you can roll a single array right-to-left and drop the space to O(n).

When to use it

Practice

Recap

• Combinatorics counts arrangements without enumerating them; the raw factorial formula overflows fast.
• Pascal's rule C(n,r) = C(n-1,r-1) + C(n-1,r) builds every coefficient with just addition.
• For large n under a prime modulus, switch to factorials plus modular inverses for O(1) queries.