LC Patterns — Combinatorics

Computing C(n, k) — pick by situation

import math
math.comb(n, k)                    # exact, no mod — one-shot, moderate n
# Under mod, many queries: precompute once —
MOD = 10**9 + 7
fact = [1] * (N + 1)
for i in range(1, N + 1): fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1): inv_fact[i-1] = inv_fact[i] * i % MOD
def C(n, k):
    if k < 0 or k > n: return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD

Third option — Pascal's row in O(k) via the ratio C(n, k+1) = C(n, k) · (n−k) // (k+1): multiply before dividing and it stays exact in integers (LC 119's intended trick).

Identities worth having on tap

• Symmetry C(n,k) = C(n,n−k); Pascal C(n,k) = C(n−1,k−1) + C(n−1,k).
• Interleaving: ways to merge two sequences of lengths m, n preserving internal order = C(m+n, m). Quietly powers half of this file.
• Subsets: Σₖ C(n,k) = 2ⁿ; permutations P(n,k) = n!/(n−k)!; multinomial n! / (a!·b!·c!).
• Catalan: Cat(n) = C(2n,n)/(n+1), recurrence Cat(n+1) = Σ Cat(i)·Cat(n−i); first values 1, 1, 2, 5, 14, 42.
• Stars and bars: non-negative solutions of x₁+…+xₖ = n is C(n+k−1, k−1).

Universal pitfalls

1. Ordered vs unordered — pairs (i, j): is (j, i) the same object? C(k,2) vs k(k−1). Decide before counting; LC 1512 vs 447 differ exactly here.
2. Overcounting without noticing — every "multiply the choices" needs the independence sentence; if stages constrain each other, the product is wrong.
3. Division under mod without a modular inverse — and C(n,k) must return 0 for k < 0 or k > n rather than crash.
4. Formula ≠ DP confusion — if bounds are small (n ≤ 1000), DP is safer under pressure and equally accepted. Say which you're choosing and why.
5. Skipping the empty case — 2ⁿ counts the empty subset; problems often exclude it (−1 at the end).

What it is: The answer decomposes into a sequence of independent decisions — count options per stage and multiply; where the structure branches into disjoint shapes, count each and add. The rest of combinatorics is this pattern with better costumes.

Intuition: good numbers (1922): each even index independently takes 5 values, each odd index 4 → 5^⌈n/2⌉ · 4^⌊n/2⌋ — huge n, so fast power finishes it. Unique digits (357): build numbers digit by digit — first digit 9 options (no 0), second 9 (0 allowed, one used), then 8, 7, … — a falling product summed over lengths. Pickup/delivery (1359): the i-th pair drops into 2i−1 gaps × i orderings → ∏ i(2i−1), discovered by hand-computing n = 1, 2.

Approach: narrate stages, verify independence ("the choice at position i doesn't restrict position j because…"), write the product, compute with a loop + mod (or fast power when stages repeat). When the count varies by a feature (length, first digit), sum over that feature's disjoint classes. Small-case verification is non-negotiable.

What it is: The object is determined by which positions get which of two labels — grid paths (which steps go right), step sequences (which steps go +1) — so the count is a single C(n, k).

Intuition: unique paths (62): any monotone path in an m×n grid is a string of (m−1) D's and (n−1) R's; the path is the choice of R-positions → C(m+n−2, m−1). Reach position after k steps (2400): to land displacement d in k unit steps, you need (k+d)/2 rights → C(k, (k+d)/2), and 0 when k+d is odd or |d| > k. Pascal's row (119): generate row n in O(k) by the running-ratio identity.

Approach: find the two-label description ("each object ↔ a choice of which k of n slots are X"); write C(n, k); guard impossible parities/ranges with 0. For the DP-vs-formula fork on 62: both accepted; formula shows insight, DP generalizes to obstacles.

What it is: Count ways to merge sequences whose internal order is fixed — shuffle two subtree orders, schedule tasks respecting per-chain order. The atom: merging lengths m and n = C(m+n, m); merging many groups = the multinomial (Σsizes)! / ∏(sizeᵢ!).

Intuition: the merged sequence is determined by which slots each group occupies (its internal order fills them uniquely). Same-BST reorderings (1569): the root must come first; left- and right-subtree elements interleave freely → ways(root) = C(L+R, L) · ways(left) · ways(right). Build rooms (1916): topological orderings of a tree = n! / ∏(subtree_size(v)).

Approach: identify the fixed-order chains/subtrees; count interleavings top-down: at each combine point multiply children's counts by the binomial distributing slots. Precompute fact/inv_fact to make every C O(1). Verify on a 3-node tree by hand.

What it is: One number sequence — 1, 1, 2, 5, 14, 42, 132… — counts a shocking family of objects: balanced parentheses, distinct BSTs, full binary trees, monotone paths staying below the diagonal, non-crossing chords. Recognize the shape, name Catalan, and the problem is done.

Intuition: the recurrence is a first-decision split: fix the first structural choice (the root; the match of the first '('), and the object splits into two smaller independent instances → Cat(n+1) = Σᵢ Cat(i)·Cat(n−i). Unique BSTs (96): choose root k → left subtree from k−1 keys, right from n−k → exactly the recurrence. Generate parentheses (22): the count is Cat(n) — a strong moment to answer "42 for n=5" mid-backtracking.

Approach: small n (all these problems): DP the convolution in O(n²) — clean and mod-safe. Closed form C(2n,n)/(n+1) (or C(2n,n) − C(2n,n+1) — subtraction form avoids inverses) when n is large.

What it is: Count pairs (or triples) of "equivalent" items — equal values, same ratio, same distance. Group items by an equivalence key with a hashmap; each group of size k contributes C(k,2) unordered or k(k−1) ordered pairs; sum over groups.

Intuition: a pair is "good" iff both members share some computable signature — so pair-counting collapses to key design plus one identity. Good pairs (1512): key = value, Σ C(k,2). Interchangeable rectangles (2001): key = reduced ratio (w//g, h//g) — never a float. Boomerangs (447): per anchor, key = squared distance; ordered pairs → Σ k(k−1). Streaming refinement: for each new item, answer += count[key] then increment — pairs counted once with i < j for free.

Approach: design the canonical key (reduce fractions by gcd; sort tuple components when order shouldn't matter; squared distances to stay integer); one pass to group (Counter); one pass over group sizes applying C(k,2) / k(k−1).

What it is: Asked for a sum over an exponential family — all subsequences, all subarrays — flip it: for each element (or pair), count how many family members it appears in (with what role), multiply, and sum. Linearity turns 2ⁿ objects into n terms.

Intuition: subsequence widths (891): Σ(max−min) over 2ⁿ subsequences — but sort (widths don't care about order) and element a[i] is the max of exactly 2^i subsequences and the min of 2^(n−1−i) → Σ a[i]·(2^i − 2^(n−1−i)). Subarray minimums (907): element a[i] is the minimum of left · right subarrays, where left/right = distances to the previous-smaller and next-smaller elements (a monotonic stack); contribution a[i]·left·right.

Approach: three steps: (1) reorder/normalize if the objective permits (sorting kills order-dependence — state why it's legal); (2) for each element, derive "in how many objects does it play role R?" — usually a power of 2 or a product of spans; (3) one pass with precomputed powers of 2 mod p. The tie-break in 907: strict-less on one side, ≤ on the other, so equal minimums count once.

What it is: Count "divisible by any of…" / "having at least one of…" where the easy counts overlap: add singles, subtract pairwise intersections, add back triples — signs alternating by subset parity. On LC the intersections are almost always LCMs.

Intuition: |A ∪ B ∪ C| = Σ|single| − Σ|pair| + |triple| — each element counted once no matter how many sets it's in. Multiples ≤ x of a: x // a; of both a and b: x // lcm(a,b) — lcm, never a·b. Nth magical (878): 2 sets + monotone count → binary search on the answer. Kth smallest coin amount (3116): up to 15 coins → iterate all 2¹⁵ subsets, sign = subset-size parity, term = x // lcm(subset).

Approach: template for the general case: for mask in 1..2^m − 1: compute l = lcm of chosen, early-break if l > x; count += (+1 if popcount odd else −1) * (x // l). Wrap in a boundary-search when the ask is "k-th" rather than "how many ≤ x". Sanity-check count(x) against a brute list for x ≤ 50.

What it is: "Return the k-th permutation/instruction-string/happy-string" with k up to billions: construct the answer position by position — at each slot, count how many objects start with each candidate prefix, and walk past whole blocks until k lands inside one.

Intuition: objects in sorted order cluster into blocks by first choice, and block sizes are computable: permutations starting with a fixed first element — (n−1)!; instruction strings starting with 'H' — C(remaining−1, remaining V's); happy strings with a fixed first char — 2^(n−1). So the k-th object's first symbol is found by subtracting block sizes from k until it fits, then recurse on the suffix. This is positional notation generalized (60 is writing k in factorial base).

Approach: convert to 0-indexed k first (k -= 1 — do it once, immediately). Per position: for each candidate symbol in sorted order, compute block = count of completions; if k >= block: k -= block else commit the symbol and descend. For 60, maintain the shrinking list of unused digits.

What it is: Count or rank numbers below a bound by their decimal structure — how many contain only certain digits, how many 1s appear across all numbers, the k-th number in lexicographic order. Model numbers as paths in a 10-ary trie; count whole subtrees, walk the boundary.

Intuition: numbers ≤ N with digits from a set (902): count by length — for lengths < len(N), free choice |D|^len; for length == len(N), walk N's digits left to right, at each position adding the count of allowed digits strictly below N[i] (each opens a free suffix), staying tight on an equal digit. K-th lexicographic number (440): the trie ordering is preorder; steps(prefix) = size of the prefix's subtree clipped to ≤ N; if k ≥ steps, move to the next sibling, else descend — unranking on the digit trie.

Approach: draw the 10-ary trie once — 902 counts leaves under allowed branches; 233 counts labeled edges; 440 navigates preorder with subtree sizes. Keep the two states of any walk explicit: tight (prefix equals N's prefix) vs free (already smaller).