Essential combinatorics functions for competitive programming and technical interviews.

*After O(n) precomputation

"How many ways to choose?" - Order doesn't matter.

Formula: C(n, r) = n! / (r! × (n-r)!)

Use Cases:

• Selecting teams from a group
• Choosing items from a set
• Counting subsets of specific size
• Grid paths (right/down movements)

Example Problems:

• Leetcode 62 - Unique Paths - Grid paths = C(m+n-2, m-1)
• Leetcode 77 - Combinations
• Choosing k elements from array

"How many ways to arrange?" - Order matters.

Formula: P(n, r) = n! / (n-r)!

Use Cases:

• Arranging people in seats
• Password generation
• Race finishing orders
• Scheduling problems

Example Problems:

• Leetcode 46 - Permutations
• Leetcode 47 - Permutations II

"How many valid structures?"

Formula: C(n) = C(2n, n) / (n+1)

Common Use Cases:

Example Problems:

• Leetcode 96 - Unique Binary Search Trees
• Leetcode 22 - Generate Parentheses
• Codeforces - Catalan Number Problems

Sequence: 1, 1, 2, 5, 14, 42, 132, 429...

"Distribute n identical items into k distinct bins"

Formula: C(n + k - 1, k - 1)

Use Cases:

• Distribute identical balls into boxes
• Coin change with unlimited coins (counting)
• Allocating resources
• Non-negative integer solutions: x₁ + x₂ + ... + xₖ = n

Example:

• Distribute 5 apples into 3 baskets = C(5+3-1, 3-1) = C(7, 2) = 21 ways

Problems:

• Codeforces 1462E1 - Distribution
• Integer partition problems

"Permutations where no element is in its original position"

Formula: D(n) = (n-1) × (D(n-1) + D(n-2))

Use Cases:

• Secret Santa (everyone gets someone else's name)
• Hat check problem
• Round-robin tournaments
• Matching problems with constraints

Example:

• D(3) = 2: [2,3,1], [3,1,2]
• D(4) = 9

Sequence: 0, 1, 2, 9, 44, 265...

When to use: Division in modular arithmetic (mod operations).

Formula: a⁻¹ ≡ a^(MOD-2) (mod MOD) (Fermat's Little Theorem, MOD is prime)

Use Case: Computing nCr with large values under modulo

• Instead of: (a / b) % MOD (WRONG)
• Use: (a × inverse(b)) % MOD (CORRECT)

Fast power calculation: Compute a^b % MOD in O(log b)

Use Cases:

• Large power calculations
• RSA cryptography basics
• Matrix exponentiation for DP

Problem: Count paths in m×n grid (only right/down moves)

Solution: C(m+n-2, m-1) or C(m+n-2, n-1)

Why? Total moves = (m-1) down + (n-1) right. Choose positions for down moves.

Problems:

• Leetcode 62 - Unique Paths
• Leetcode 63 - Unique Paths II

Problem: Choose k items from n items

Solution: C(n, k)

Problems:

• Leetcode 77 - Combinations
• Team selection problems

Problem: Count structurally unique BSTs with n nodes

Solution: Catalan(n)

Problems:

• Leetcode 96 - Unique Binary Search Trees

Problem: Count valid parentheses combinations with n pairs

Solution: Catalan(n)

Problems:

• Leetcode 22 - Generate Parentheses

Problem: Climb n stairs with [1, 2, 3, ...] steps allowed

Solution:

• 1 or 2 steps → Fibonacci
• General case → DP or combinatorics

Problems:

• Leetcode 70 - Climbing Stairs
• Leetcode 746 - Min Cost Climbing Stairs

✅ Use precomputation when:

• Multiple queries (Q > 100)
• Max n ≤ 10^6
• Time limit is tight

❌ Don't precompute when:

• Single query
• n is very large (> 10^7)
• Space is limited

• nCrDirect: Small n, no modulo needed (n ≤ 20)
• nCr (precomputed): Multiple queries, needs modulo, n ≤ 10^6

1. Overflow: Use long for intermediate calculations
2. Division in mod: Use modular inverse, not direct division
3. Range: Ensure n doesn't exceed precomputed range
4. Edge cases: C(n, 0) = 1, C(n, n) = 1, C(n, r) = 0 if r > n

• Leetcode 70 - Climbing Stairs
• Leetcode 62 - Unique Paths
• Leetcode 77 - Combinations

• Leetcode 96 - Unique Binary Search Trees
• Leetcode 22 - Generate Parentheses
• Codeforces - Combinatorics Tag

• Leetcode 1569 - Number of Ways to Reorder Array
• Codeforces - Combinatorics + Math
• Problems involving Lucas Theorem (very large n, small mod)

Precomputation: O(n) Space: O(n) Query (nCr, nPr, factorial): O(1) Modular operations: O(log MOD)

Memory: ~24n bytes (3 arrays of size n)

// Initialize once
Combinatorics comb = new Combinatorics(100000);

// Fast queries
long ways = comb.nCr(n, k);  // O(1)
long arrangements = comb.nPr(n, k);  // O(1)
long bsts = comb.catalan(n);  // O(1)

Note: All operations use MOD = 10^9 + 7 by default (common in competitive programming).