MathAlgorithmaka binomial coefficient, nCr, Pascal's triangle, stars and bars, inclusion-exclusion

Combinatorics

Count arrangements and selections: nCr via factorial and inverse-factorial tables mod p, Pascal's triangle, stars and bars, and inclusion-exclusion.

Pattern: Dynamic ProgrammingPractice (4)
Progress

Overview

The binomial coefficient C(n, k) = n! / (k! (n-k)!) counts the ways to choose k of n items. Four ways to compute it. Factorial tables mod a prime: precompute fact[i] and invfact[i] for i ≤ N once in O(N), then each C(n, k) = fact[n] · invfact[k] · invfact[n-k] mod p is O(1) — the workhorse when many queries and a modulus are involved (see Modular Inverse). Pascal's triangle: C(n, k) = C(n-1, k-1) + C(n-1, k), an O(n²) DP that needs no division and works with any modulus or with big integers. Multiplicative formula: C(n, k) = Π_{i=1..k} (n - k + i) / i, exact in O(k) without a modulus. Lucas' theorem for n far above the table size with a small prime modulus.

Stars and bars: the number of ways to write n as an ordered sum of k non-negative integers is C(n + k - 1, k - 1) — picture n stars split by k - 1 bars. With each part at least 1 it is C(n - 1, k - 1). Permutations P(n, k) = n! / (n-k)!, arrangements with repeats n! / (a! b! …), and derangements D(n) = (n-1)(D(n-1) + D(n-2)) round out the toolkit.

Inclusion-exclusion counts a union by alternating sums: |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|. Over m conditions it iterates all 2^m subsets of conditions (see Subset Generation with Bitmasks) with sign (-1)^(|S|). Typical use: count numbers ≤ N divisible by none of a list of primes, or strings avoiding a set of forbidden patterns.

nCrbinomialPascalfactorialstars and barsinclusion-exclusioncounting

Intuition

A mental model before the formal terms.

Choosing a committee of 3 from 10 people: line everyone up and pick — 10 · 9 · 8 ordered picks — but each committee was counted 3! = 6 times (once per ordering), so divide: 720 / 6 = 120. Every nCr formula is this "count ordered, then divide out the over-count" idea; mod p the division becomes multiplication by an inverse.

Stars and bars: to hand 7 identical candies to 3 children, lay the 7 candies in a row and drop 2 dividers somewhere among them. Each placement of dividers is a distribution and vice versa, so count arrangements of 7 stars and 2 bars: C(9, 2) = 36.

Inclusion-exclusion: counting students in "math or physics" by adding class sizes double-counts those in both — subtract them once. With three clubs, the triple members were added 3 times, subtracted 3 times, so add them back once.

How it works

  1. Tables mod prime p (N < p): fact[0] = 1; fact[i] = fact[i-1] · i. invfact[N] = fact[N]^(p-2) by Fast Exponentiation; invfact[i-1] = invfact[i] · i. Then C(n, k) = fact[n] · invfact[k] % p · invfact[n-k] % p, returning 0 if k < 0 or k > n.
  2. Pascal: C[0][0] = 1; for each row n, C[n][0] = C[n][n] = 1 and C[n][k] = C[n-1][k-1] + C[n-1][k], reducing mod m if needed. A single rolling row updated from right to left saves memory.
  3. Multiplicative (exact, no modulus): res = 1; for i in 1..k: res = res · (n - k + i) / i — the division is always exact at each step.
  4. Stars and bars: translate "non-negative solutions of x1 + … + xk = n" to C(n + k - 1, k - 1); for lower bounds subtract them from n first; for upper bounds apply inclusion-exclusion over violated bounds.
  5. Inclusion-exclusion over m sets: iterate masks 1..2^m - 1, compute the size of the intersection for that mask, add it with sign + for odd popcount and - for even (see Count Set Bits (Popcount)).

Why it works

C(n, k): there are n! orderings of all items; fixing the first k as the chosen set, the k! orderings inside and (n-k)! outside describe the same choice, so n! / (k!(n-k)!) distinct choices. Mod p with n < p, none of the factorials is divisible by p, so their inverses exist.

Pascal: either the last item is in the chosen set (choose k - 1 from the rest) or not (choose k from the rest); the cases are disjoint and exhaustive.

Stars and bars: an arrangement of n stars and k - 1 bars is determined by which k - 1 of the n + k - 1 positions hold bars, and it encodes exactly one composition of n into k ordered non-negative parts.

Inclusion-exclusion: an element in exactly t ≥ 1 of the sets is counted C(t,1) - C(t,2) + C(t,3) - … = 1 - (1-1)^t = 1 time by the alternating sum, so every element of the union is counted once.

Recognition

How to tell a problem wants this.

  • "How many ways", "number of arrangements/selections/distributions", especially "modulo 10^9 + 7".
  • Lattice-path counting (C(m+n-2, m-1) for a grid — the closed form of Grid DP unique paths).
  • Distributing identical items into distinct bins; solutions of x1 + … + xk = n.
  • "Count numbers not divisible by any of", "strings containing at least one of", "at least / at most" conditions over several properties — inclusion-exclusion.
“number of ways” → Dynamic Programming“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1precompute(N, p):
2  fact[0] = 1; for i in 1..N: fact[i] = fact[i-1] * i mod p
3  invfact[N] = power(fact[N], p - 2, p)
4  for i in N..1: invfact[i-1] = invfact[i] * i mod p
5C(n, k) = 0 if k < 0 or k > n else fact[n] * invfact[k] * invfact[n-k] mod p
6stars_and_bars(n, k) = C(n + k - 1, k - 1)
7inclusion_exclusion(sets): sum over nonempty S: (-1)^(|S|+1) * |intersection(S)|

Implementations

1import math
2 
3# Counting without enumerating. n choose k is the workhorse; modular
4# factorials plus inverse factorials make it O(1) per query after O(n) setup.
5MOD = 1_000_000_007
6 
7 
81 · Pascal's triangle: exact for small n, and needs no modular inverse
9def pascal(n: int, mod: int = MOD) -> list[list[int]]:
10    c: list[list[int]] = []
11    for i in range(n + 1):
12        row = [1] * (i + 1)
13        for j in range(1, i):
14            row[j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod
15        c.append(row)
16    return c
17 
18 
192 · Factorial and inverse-factorial tables, built in O(n) with one pow
20class Binomials:
21    def __init__(self, n: int, mod: int = MOD) -> None:
22        self.mod = mod
23        self.fact = [1] * (n + 1)
24        for i in range(1, n + 1):
25            self.fact[i] = self.fact[i - 1] * i % mod
26        # One exponentiation for the last one, then walk backwards
27        self.inv_fact = [1] * (n + 1)
28        self.inv_fact[n] = pow(self.fact[n], mod - 2, mod)
29        for i in range(n, 0, -1):
30            self.inv_fact[i - 1] = self.inv_fact[i] * i % mod
31 
323 · C(n, k) = n! / (k! (n-k)!), with division as inverse multiplication
33    def choose(self, n: int, k: int) -> int:
34        if k < 0 or k > n:
35            return 0
36        return self.fact[n] * self.inv_fact[k] % self.mod * self.inv_fact[n - k] % self.mod
37 
384 · Permutations P(n, k) = n! / (n-k)! — the same table, one factor fewer
39    def permute(self, n: int, k: int) -> int:
40        if k < 0 or k > n:
41            return 0
42        return self.fact[n] * self.inv_fact[n - k] % self.mod
43 
44 
455 · Stars and bars: ways to put n identical items into k labelled boxes
46def stars_and_bars(n: int, k: int, b: Binomials) -> int:
47    return b.choose(n + k - 1, k - 1)
48 
49 
50# Exact (non-modular) answers come straight from the standard library
51def exact_choose(n: int, k: int) -> int:
52    return math.comb(n, k)
Walkthrough
  1. math.comb(n, k) gives the *exact* binomial coefficient with no modulus, which is often all that is needed — Python is the only one of the four with this built in.
  2. The modular class exists for problems that demand answers mod a prime, where exact values would have millions of digits.
  3. pow(self.fact[n], mod - 2, mod) is the single built-in modular exponentiation that seeds the backward inverse-factorial walk.
  4. self.fact[i - 1] * i % mod relies on * and % having equal precedence and left associativity, so it reduces after the multiply.
  5. Pascal's triangle builds each row from the previous one and works for any modulus, prime or not.
Complexity (this implementation)
time O(n^2) for Pascal; O(n) setup then O(1) per choose/permute · space O(n^2) for Pascal; O(n) for the tables

math.comb is C-implemented and exact; for n around 10^6 the result has hundreds of thousands of digits, which is when the modular version becomes necessary.

Language notes
  • math.comb(n, k) and math.perm(n, k) (Python 3.8+) give exact binomials and permutations directly.
  • math.factorial(n) is exact and C-implemented, but produces enormous integers for large n.
  • itertools.combinations and permutations *enumerate* rather than count — using len(list(...)) to count is exponential and is the classic misuse.
  • functools.lru_cache on a recursive choose is a common alternative, exact but with O(n*k) memory.
Common mistakes in this language
  • Counting with len(list(itertools.combinations(range(n), k))), which enumerates every subset and is hopeless past n = 30.
  • Using the Fermat-based table with a composite modulus.
  • Reaching for the modular class when math.comb would do, since exact answers are free in Python for moderate n.
Language differences that matter here
  • Python is the only language with binomials built in (math.comb, math.perm), and its unbounded integers make the *exact* answer available for free where the others must work modulo a prime.
  • The modular route needs BigInt in JS/TS and __int128 widening in C++; in Python it is plain integer arithmetic with a %.
  • API typing: JS/TS mix number indices with bigint values, which TypeScript makes explicit and JavaScript leaves as a runtime hazard (return 0 instead of 0n).
  • The counting-versus-enumerating trap is specific to Python, where itertools.combinations is close enough to math.comb in name and spirit to be misused as a counter.

Complexity

Best
O(1)
Average
O(1)
Worst
O(n^2)
Space
O(n)

Factorial tables: O(N) precomputation (plus one O(log p) exponentiation), then O(1) per C(n, k). Pascal: O(n^2) time and space (O(n) with a rolling row). Multiplicative formula: O(k). Inclusion-exclusion over m sets: O(2^m · m).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Many nCr queries modulo a prime with n up to a few million — factorial and inverse-factorial tables.
  • Composite or unspecified modulus, or exact big-integer values for small n — Pascal's triangle.
  • Counting distributions of identical items, or integer solutions to linear equations with bounds — stars and bars.
  • Counting objects that avoid or satisfy "at least one" of a few conditions — inclusion-exclusion.
Avoid it when
  • n ≥ p with factorial tables: fact[n] ≡ 0, and the inverse does not exist. Use Lucas' theorem (C(n, k) ≡ Π C(n_i, k_i) over base-p digits) for small p.
  • Inclusion-exclusion with more than ~20 conditions — 2^m terms; look for a DP or a Möbius-function formulation.
  • Distinguishable-vs-indistinguishable confusion: stars and bars counts identical items in distinct bins only. Distinct items in distinct bins is k^n; identical items in identical bins is integer partitions (a DP).

Alternatives

Grid DPSubset Generation with BitmasksDynamic Programming

Common mistakes

  • Computing n! / (k! (n-k)!) with integer division after reducing mod p — use inverse factorials.
  • Building the inverse-factorial table from invfact[i] = powMod(fact[i], p-2) for every i — correct but O(N log p); the downward recurrence is O(N).
  • Not returning 0 for k > n or k < 0, leading to out-of-bounds table access or wrong sums.
  • JavaScript: multiplying two residues near 10^9 as plain numbers; the tables must be BigInt (or use a modulus below 2^26 with splitting).
  • Stars and bars off by one: non-negative parts give C(n + k - 1, k - 1), positive parts give C(n - 1, k - 1).
  • Inclusion-exclusion sign errors — odd-size intersections are added, even-size subtracted; verify with a tiny hand example.

Interview patterns

  • Unique Paths as C(m + n - 2, m - 1) instead of a grid DP.
  • Number of ways to form a target with limited item counts: stars and bars plus inclusion-exclusion over upper bounds.
  • Pascal's Triangle rows (LeetCode 118/119) and "count subsequences of length k" queries mod 10^9 + 7.
  • Count strings/permutations avoiding a set of forbidden patterns, or numbers ≤ N coprime to a given m (φ-style) via inclusion-exclusion over prime factors of m.
Interview questions on this
Mock interviews

Example problems

SubsetsmediumClimbing StairseasyUnique PathsmediumCount Primesmedium