Combinatorics

Topic type: Math / Theory
LeetCode tag size: ~55 problems → depth: core algorithms, main patterns, key complexities

math.md covers the counting toolkit (C(n,k) formula, P(n,r), Pascal's triangle, stars & bars, inclusion-exclusion, precomputed factorials mod p, Lucas' theorem). This file assumes that infrastructure and focuses on the combinatorial structures and proof techniques built on top of it. See math.md for full coverage of that toolkit.

---

Core Concepts

Fundamental counting principle — if event A can occur in m ways and event B independently in n ways, the pair can occur in m·n ways (product rule). If A and B are mutually exclusive, total = m + n (sum rule).

Bijection — a one-to-one correspondence between two sets proves they have equal cardinality without computing either directly. Recognising the bijection is often the entire insight in a hard problem.

Complement counting — compute total − invalid when invalid cases are structurally simpler than valid ones.

Multinomial coefficient — n! / (k₁! k₂! … kₘ!) where k₁+…+kₘ = n; counts distinct permutations of a multiset of sizes k₁,…,kₘ, or distributions of n labeled items into m labeled groups of fixed sizes.

Circular permutation — (n−1)! arrangements of n distinct items around a circle; one item is pinned to eliminate rotational equivalence, leaving (n−1)! orderings.

Catalan number — Cₙ = C(2n,n)/(n+1); counts balanced parenthesisations, triangulations of an (n+2)-gon, non-crossing handshakes, unique BSTs with n keys. Satisfies C₀=1 and the convolution recurrence below.

Derangement D(n) — permutation of n elements where every element is displaced from its original position. D(0)=1, D(1)=0, D(2)=1. Asymptotically D(n)/n! → 1/e ≈ 0.368.

Stirling number of the second kind S(n,k) — number of ways to partition n labeled elements into exactly k non-empty unlabeled subsets. S(n,1)=1, S(n,n)=1, S(n,k)=0 for k>n.

Bell number B(n) — total number of set partitions of n elements; B(n) = Σₖ S(n,k). B(0)=B(1)=1, B(2)=2, B(3)=5, B(4)=15.

---

Types / Variants

---

Key Algorithms

Catalan Numbers

Counts binary trees, balanced brackets, triangulations, non-crossing partitions, and valid BSTs with n keys.

Closed form: Cₙ = C(2n,n)/(n+1) — O(1) with precomputed factorials.

Recurrence: C₀=1, Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ · Cₙ₋₁₋ᵢ — O(n²) DP; each Cₙ splits the structure at the first boundary into a left part of size i and a right part of size n−1−i.

Growth: Cₙ ~ 4ⁿ / (n^(3/2) √π) — overflows 64-bit integers around n=35.

Derangements

Recurrence (O(n), O(1) space with two variables):

D[n] = (n - 1) * (D[n-1] + D[n-2])

Inclusion-exclusion form: D(n) = n! · Σₖ₌₀ⁿ (−1)ᵏ/k! — useful for deriving the formula; the recurrence is faster to compute.

D(n) mod p: use the recurrence; do not expand the inclusion-exclusion sum for large n.

Multinomial Coefficient

n! / (k₁! k₂! … kₘ!) — use precomputed factorials and modular inverses (see math.md).

Key application: counting anagram-like arrangements. For the string with character frequencies k₁,…,kₘ, distinct permutations = n!/∏kᵢ!

Burnside's Lemma

Counts distinct objects under a symmetry group G (rotations, reflections):

|Orbits| = (1/|G|) · Σᵍ∈G |Fix(g)|

where Fix(g) = number of colorings/arrangements fixed by symmetry g. For a necklace of n beads with c colors, applying rotations gives |G|=n and |Fix(rotation by k)| = c^gcd(k,n). Time: O(|G| · cost of computing Fix(g)).

Use when the problem asks to count arrangements "up to rotation" or "up to symmetry." Do not use when positions are labeled (no symmetry equivalence).

Stirling Numbers (Second Kind)

Recurrence: S(n,k) = k·S(n−1,k) + S(n−1,k−1)

Interpretation: when adding element n to an existing partition, either place it in one of the k existing subsets (k choices) or start a new singleton subset (+1 subset).

S[n][k] = k * S[n-1][k] + S[n-1][k-1]

Time: O(n·k). Only store two rows (rolling) if space is critical.

k-th Lexicographic Permutation (Factorial Number System)

To find the k-th (1-indexed) permutation of n items: divide k−1 successively by (n−1)!, (n−2)!, … The quotient at each step indexes the next digit in the remaining elements.

k -= 1
for i in range(n, 0, -1):
    idx, k = divmod(k, factorial(i - 1))
    # pick elements[idx], remove it

O(n²) naively, O(n log n) with a Fenwick tree for the removal.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• k > n in C(n,k): result is 0, not an error; guard this before calling factorial-based formulas.
• D(0) = 1, D(1) = 0: the empty permutation is a derangement by convention; D(1)=0 because the single element must stay — not displace. Getting these wrong corrupts the entire recurrence.
• Circular vs. linear: circular permutation is (n−1)!, not n!. Forgetting to divide by n (or pin one element) over-counts by a factor of n.
• Stars and bars empty vs. non-empty bins: allowing empty bins → C(n+k−1, k−1); requiring ≥1 per bin → C(n−1, k−1). The two formulas are commonly swapped.
• Catalan recurrence indexing: Cₙ = Σᵢ₌₀ⁿ⁻¹ Cᵢ · Cₙ₋₁₋ᵢ, not Σ Cᵢ · Cₙ₋ᵢ. Off-by-one in the upper index produces wrong values silently.
• Stirling first vs. second kind: S(n,k) second kind = set partitions; first kind = permutations by cycle count. They are distinct; don't use one formula for the other.
• Burnside Fix(g) computation: Fix(g) is not the same as the size of the orbit; it counts arrangements that are globally unchanged by g, which often reduces to a smaller combinatorial subproblem.
• Overflow before mod: apply mod after each multiplication, not only at the end; a * b % p not (a * b) % p when a·b exceeds 64-bit range.

---

Implementation Notes

• Python math.comb(n, k) is exact arbitrary-precision; use it for small inputs or exact counting. For modular answers, switch to precomputed fact[] / inv_fact[] (see math.md).
• Derangement: the two-variable recurrence D[n] = (n-1)*(D[n-1]+D[n-2]) avoids the O(n) inclusion-exclusion sum; store only the previous two values.
• Catalan: math.comb(2*n, n) // (n+1) is exact in Python for small n. For mod p, use fact[2*n] * inv_fact[n] * inv_fact[n+1] % p.
• Stirling table: only half the n×k grid is non-zero (k ≤ n), so allocate accordingly. A rolling two-row approach halves memory if only the final row is needed.
• Burnside: the loop over g ∈ G is O(|G|), and |G| is often n (cyclic group). Computing Fix(rotation by k) as c^gcd(k,n) requires only a GCD + fast exponentiation per step.
• Factorial number system: precompute factorial values up to n; divide k by (n−1)! down to 0! to extract each digit. Use a sorted list and pop by index for correctness.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Grid / Lattice Paths

• LC 62 Unique Paths — C(m+n−2, m−1)
• LC 63 Unique Paths II — DP with obstacles
• LC 1643 Kth Smallest Instructions — C(n,k) on remaining steps

Catalan Numbers

• LC 96 Unique Binary Search Trees — direct Catalan application
• LC 95 Unique Binary Search Trees II — enumerate (same count, different output)

Arrangement Counting

• LC 1359 Count All Valid Pickup and Delivery Options — factored counting of dependent choices
• LC 2514 Count Anagrams — multinomial coefficient per word
• LC 2954 Count the Number of Infection Sequences — factorial + modular inverse

Hard / Advanced

• LC 1866 Number of Ways to Rearrange Sticks With K Sticks Visible — Stirling S(n,k) second kind
• LC 1735 Count Ways to Make Array With Product — factored combinatorics on prime exponents
• LC 2338 Count the Number of Ideal Arrays — combinatorics on divisor chains
• LC 3343 Count Number of Balanced Permutations — multinomial with parity constraint

Clarification Questions to Ask

• Are items distinguishable (labeled) or identical? This is the single most important question.
• Does the order of selection/arrangement matter?
• Are repetitions / reuse allowed?
• Are containers / slots distinguishable?
• Is the answer expected modulo some prime p, or exact? (Determines whether to use precomputed factorials or exact arithmetic.)
• For circular problems: are rotations considered identical? Are reflections?

Common Interview Mistakes

• Using P(n,k) when C(n,k) is correct — failing to notice that order is irrelevant.
• Forgetting to apply mod after each multiplication, then overflowing before the final mod.
• Stars-and-bars formula confusion: C(n+k−1,k−1) for empty bins allowed vs. C(n−1,k−1) for at least 1 per bin.
• Catalan recurrence off-by-one: summing Cᵢ·Cₙ₋ᵢ (wrong) instead of Cᵢ·Cₙ₋₁₋ᵢ (correct).
• Treating D(0) as 0 or undefined instead of 1; treating D(1) as 1 instead of 0.
• Applying Burnside's lemma without checking whether reflections are also symmetries (dihedral vs. cyclic group).

Typical Follow-Up Escalations

• "Output mod 10^9+7" → precompute fact[] and inv_fact[] of size n; O(1) per query.
• "What if arrangements are circular?" → use (n−1)! instead of n!; fix one element and permute the rest.
• "What if items are not all distinct?" → multinomial n!/(k₁!·k₂!·…); divide by the product of group factorials.
• "Count distinct necklaces under rotation" → Burnside's lemma; |Fix(rotation by k)| = c^gcd(k,n).
• "What if the modulus is not prime?" → Fermat inverse fails; use extended Euclidean GCD for modular inverse; for very composite moduli, use Lucas' theorem with prime power decomposition.