{"title":"Combinatorics","description":"","content":"Combinatorics is the study of counting, and it shows up in coding interviews whenever a problem asks \"how many ways\" something can be done.\n\nA direct approach quickly becomes infeasible as input sizes grow. Combinatorics provides closed-form tools that count without enumeration. The rest of this chapter covers permutations and combinations, Pascal's triangle, the standard identities, `nCr` under a modulus, and the stars-and-bars technique.\n\n---\n\n# Permutations vs Combinations\n\nThe two fundamental building blocks of combinatorics are permutations and combinations. The difference comes down to one question: does order matter?\n\n- **Permutation (nPr):** The number of ways to arrange r items from n items where order matters.\n- **Combination (nCr):** The number of ways to choose r items from n items where order does not matter.\n\n**Formula for Permutations:**\n\n\n```shell\nP(n, r) = n! / (n - r)!\n```\n\n\n**Formula for Combinations:**\n\n\n```shell\nC(n, r) = n! / (r! * (n - r)!)\n```\n\n\nNotice that C(n, r) = P(n, r) / r!, because combinations remove the r! orderings that permutations count separately.\n\n\n```mermaid\nflowchart TD\n Q[\"Counting Problem\"]:::primary\n Q --> D{\"Does order
matter?\"}:::orange\n D -->|Yes| P[\"Permutation
P(n, r) = n! / (n-r)!\"]:::green\n D -->|No| C[\"Combination
C(n, r) = n! / (r! * (n-r)!)\"]:::teal\n\n P --> PE[\"Example: Arranging
3 books on a shelf
from 5 books = 60\"]:::primary\n C --> CE[\"Example: Choosing
3 books to read
from 5 books = 10\"]:::primary\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n**Quick example:** From a group of 5 people {A, B, C, D, E}, suppose we want to pick 3.\n\n- **Permutations** (order matters): ABC, ACB, BAC, BCA, CAB, CBA are all different. P(5,3) = 5! / 2! = 60.\n- **Combinations** (order does not matter): {A, B, C} is the same regardless of order. C(5,3) = 5! / (3! * 2!) = 10.\n\n---\n\n# Factorials and Their Properties\n\nThe factorial function is the foundation of all combinatorial formulas. For a non-negative integer n:\n\n\n```shell\nn! = n * (n-1) * (n-2) * ... * 2 * 1\n0! = 1 (by definition)\n```\n\n\nKey properties you should know:\n\n- **Recursive definition:** n! = n * (n-1)!\n- **Growth rate:** Factorials grow fast. 20! ≈ 2.43 × 10^18 is the largest factorial that fits in a 64-bit signed integer. 21! (about 5.1 × 10^19) overflows.\n- **Cancellation trick:** When computing C(n, r), you do not need to compute the full factorials. For example, C(10, 3) = (10 * 9 * 8) / (3 * 2 * 1) = 120. The (n-r)! in the denominator cancels most of the numerator.\n\n---\n\n# Pascal's Triangle\n\nPascal's Triangle is one of the most elegant structures in mathematics, and it gives us a way to compute C(n, r) without ever computing a factorial.\n\nThe idea is simple. Each entry in the triangle is the sum of the two entries directly above it:\n\n\n```shell\nC(n, r) = C(n-1, r-1) + C(n-1, r)\n```\n\n\nThis is called Pascal's identity. It works because choosing r items from n items can be split into two cases: either a specific item is included (leaving C(n-1, r-1) choices) or it is not (leaving C(n-1, r) choices).\n\nHere is what the first six rows look like:\n\n\n```shell\nRow 0: 1\nRow 1: 1 1\nRow 2: 1 2 1\nRow 3: 1 3 3 1\nRow 4: 1 4 6 4 1\nRow 5: 1 5 10 10 5 1\n```\n\n\n---\n\n# Common Combinatorial Identities\n\nBefore we move to implementation, here are identities you should know.\n\n\n| Identity | Formula | Meaning |\n|----------|---------|---------|\n| Symmetry | C(n, r) = C(n, n-r) | Choosing r to include = choosing n-r to exclude |\n| Row sum | C(n,0) + C(n,1) + ... + C(n,n) = 2^n | Total subsets of an n-element set |\n| Pascal's identity | C(n, r) = C(n-1, r-1) + C(n-1, r) | Include or exclude one element |\n| Vandermonde's identity | C(m+n, r) = sum of C(m,k)*C(n,r-k) | Choosing from two groups |\n| Hockey stick | C(r,r) + C(r+1,r) + ... + C(n,r) = C(n+1, r+1) | Sum along a diagonal |\n\n\nThe symmetry identity is especially useful for optimization. If you need C(100, 97), compute C(100, 3) instead, which requires far fewer multiplications.\n\n---\n\n# nCr with Modular Arithmetic\n\nWhen n is large (say, up to 10^6), the values of C(n, r) become astronomically large. Interview problems typically ask you to return the answer modulo 10^9 + 7 (a prime number). This is where modular arithmetic becomes essential.\n\nThe approach has three parts:\n\n1. **Precompute factorials** mod p: fact[i] = i! mod p\n2. **Precompute inverse factorials** mod p: inv_fact[i] = (i!)^(-1) mod p\n3. **Compute nCr** as: fact[n] * inv_fact[r] * inv_fact[n-r] mod p\n\nTo compute modular inverse, we use Fermat's little theorem. For a prime p:\n\n\n```shell\na^(-1) mod p = a^(p-2) mod p\n```\n\n\nThis works because a^(p-1) = 1 (mod p) for any a not divisible by p, so a^(p-2) * a = 1 (mod p).\n\n\n```mermaid\nflowchart LR\n A[\"Precompute
fact[0..n]\"]:::primary --> B[\"Compute
inv_fact[n] = fact[n]^(p-2)\"]:::orange\n B --> C[\"Fill inv_fact
backwards:
inv_fact[i] = inv_fact[i+1] * (i+1)\"]:::teal\n C --> D[\"nCr =
fact[n] * inv_fact[r]
* inv_fact[n-r]
mod p\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe key optimization is computing `inv_fact` backwards. Instead of calling modular exponentiation `n` times, we compute `inv_fact[n]` once using fast exponentiation, then derive the rest with `inv_fact[i] = inv_fact[i+1] · (i+1) mod p` going downward. This brings the total precomputation to O(n) time.\n\nThe recurrence falls out of one identity. By definition, `(i+1)! = (i+1) · i!`. Divide both sides by `(i+1)! · i!`:\n\n`1/i! = (i+1) · 1/(i+1)!`\n\nThat is exactly `inv_fact[i] = (i+1) · inv_fact[i+1]`, reduced modulo `p`. So one expensive `modPow` call seeds `inv_fact[n]`, and the rest is a single multiplication per step.\n\n---\n\n# Stars and Bars Technique\n\nThe stars and bars technique answers a classic question: how many ways can you distribute n identical items into k distinct bins?\n\nThe answer is C(n + k - 1, k - 1).\n\nThe intuition is beautiful. Imagine n stars in a row representing the items. You need k-1 bars to separate them into k groups. The total number of symbols is n + k - 1, and you are choosing where to place the k - 1 bars.\n\n**Example:** Distribute 5 identical balls into 3 bins.\n\nWe need C(5 + 3 - 1, 3 - 1) = C(7, 2) = 21 ways.\n\nOne such distribution: `**|*|**` means 2 balls in bin 1, 1 in bin 2, 2 in bin 3.\n\nThis technique is the foundation for many interview problems involving distributing resources, partitioning numbers, or counting solutions to equations like x1 + x2 + x3 = n where xi >= 0.\n\n---\n\n# Example Walkthroughs\n\n### Example 1: Building Pascal's Triangle\n\nLet us build the first 5 rows step by step.\n\n\n```shell\nStart: dp[0] = [1]\n\nRow 1: dp[1][0] = 1, dp[1][1] = 1\n Result: [1, 1]\n\nRow 2: dp[2][0] = 1\n dp[2][1] = dp[1][0] + dp[1][1] = 1 + 1 = 2\n dp[2][2] = 1\n Result: [1, 2, 1]\n\nRow 3: dp[3][0] = 1\n dp[3][1] = dp[2][0] + dp[2][1] = 1 + 2 = 3\n dp[3][2] = dp[2][1] + dp[2][2] = 2 + 1 = 3\n dp[3][3] = 1\n Result: [1, 3, 3, 1]\n\nRow 4: dp[4][0] = 1\n dp[4][1] = dp[3][0] + dp[3][1] = 1 + 3 = 4\n dp[4][2] = dp[3][1] + dp[3][2] = 3 + 3 = 6\n dp[4][3] = dp[3][2] + dp[3][3] = 3 + 1 = 4\n dp[4][4] = 1\n Result: [1, 4, 6, 4, 1]\n```\n\n\n### Example 2: Computing C(10, 3)\n\nUsing the cancellation trick:\n\n\n```shell\nC(10, 3) = 10! / (3! * 7!)\n = (10 * 9 * 8) / (3 * 2 * 1)\n = 720 / 6\n = 120\n```\n\n\nThere are 120 ways to choose 3 items from 10.\n\n### Example 3: Grid Paths\n\nHow many unique paths are there from the top-left to the bottom-right of a 4x3 grid, moving only right or down?\n\nTo go from (0,0) to (3,2), we must make exactly 3 right moves and 2 down moves, for a total of 5 moves. The number of paths is the number of ways to choose which 2 of the 5 moves are \"down\" (or equivalently, which 3 are \"right\"):\n\n\n```shell\nC(5, 2) = 5! / (2! * 3!) = (5 * 4) / (2 * 1) = 10\n```\n\n\nMore generally, for an m x n grid: paths = C(m + n - 2, m - 1).\n\n---\n\n# Implementation\n\nBelow are three implementations: factorial-based nCr (for small values), Pascal's Triangle via DP, and nCr with modular arithmetic using precomputed factorials and inverse factorials.\n\n### Approach 1: Factorial-Based nCr (Small Values)\n\nThis approach computes nCr directly using the cancellation trick. It works well for small n (roughly n < 20 to avoid overflow without modular arithmetic).\n\n\n```java\npublic class Combinatorics {\n // Computes C(n, r) using the multiplicative formula\n // Works for small n without overflow concerns\n public static long nCr(int n, int r) {\n if (r > n) return 0;\n if (r == 0 || r == n) return 1;\n // Use symmetry: C(n, r) = C(n, n-r)\n if (r > n - r) r = n - r;\n\n long result = 1;\n for (int i = 0; i < r; i++) {\n result = result * (n - i) / (i + 1);\n }\n return result;\n }\n}\n```\n\n```python\ndef nCr(n: int, r: int) -> int:\n if r > n:\n return 0\n if r == 0 or r == n:\n return 1\n # Use symmetry: C(n, r) = C(n, n-r)\n if r > n - r:\n r = n - r\n\n result = 1\n for i in range(r):\n result = result * (n - i) // (i + 1)\n return result\n```\n\n```cpp\nlong long nCr(int n, int r) {\n if (r > n) return 0;\n if (r == 0 || r == n) return 1;\n if (r > n - r) r = n - r;\n\n long long result = 1;\n for (int i = 0; i < r; i++) {\n result = result * (n - i) / (i + 1);\n }\n return result;\n}\n```\n\n```go\npackage main\n\n// Computes C(n, r) using the multiplicative formula\n// Works for small n without overflow concerns\nfunc nCr(n int, r int) int64 {\n\tif r > n {\n\t\treturn 0\n\t}\n\tif r == 0 || r == n {\n\t\treturn 1\n\t}\n\t// Use symmetry: C(n, r) = C(n, n-r)\n\tif r > n-r {\n\t\tr = n - r\n\t}\n\n\tvar result int64 = 1\n\tfor i := 0; i < r; i++ {\n\t\tresult = result * int64(n-i) / int64(i+1)\n\t}\n\treturn result\n}\n```\n\n```csharp\npublic class Combinatorics {\n public static long NCr(int n, int r) {\n if (r > n) return 0;\n if (r == 0 || r == n) return 1;\n if (r > n - r) r = n - r;\n\n long result = 1;\n for (int i = 0; i < r; i++) {\n result = result * (n - i) / (i + 1);\n }\n return result;\n }\n}\n```\n\n```rust\npub struct Combinatorics;\n\nimpl Combinatorics {\n // Computes C(n, r) using the multiplicative formula\n // Works for small n without overflow concerns\n pub fn nCr(n: i32, mut r: i32) -> i64 {\n if r > n {\n return 0;\n }\n if r == 0 || r == n {\n return 1;\n }\n // Use symmetry: C(n, r) = C(n, n-r)\n if r > n - r {\n r = n - r;\n }\n\n let mut result: i64 = 1;\n for i in 0..r {\n result = result * (n - i) as i64 / (i + 1) as i64;\n }\n result\n }\n}\n```\n\n```javascript\n// Uses BigInt because the running product exceeds Number.MAX_SAFE_INTEGER (2^53)\n// around n = 60 even for moderate r.\nfunction nCr(n, r) {\n if (r > n) return 0n;\n if (r === 0 || r === n) return 1n;\n if (r > n - r) r = n - r;\n\n let result = 1n;\n const bn = BigInt(n);\n for (let i = 0n; i < BigInt(r); i++) {\n result = result * (bn - i) / (i + 1n);\n }\n return result;\n}\n```\n\n```typescript\n// Uses bigint because the running product exceeds Number.MAX_SAFE_INTEGER (2^53)\n// around n = 60 even for moderate r.\nfunction nCr(n: number, r: number): bigint {\n if (r > n) return 0n;\n if (r === 0 || r === n) return 1n;\n if (r > n - r) r = n - r;\n\n let result = 1n;\n const bn = BigInt(n);\n for (let i = 0n; i < BigInt(r); i++) {\n result = result * (bn - i) / (i + 1n);\n }\n return result;\n}\n```\n\n\n---\n\n### Approach 2: Pascal's Triangle (DP)\n\nThis approach builds the entire triangle up to row n. It is useful when you need multiple nCr values for the same n, or when you want to avoid division entirely.\n\n\n```java\npublic class PascalTriangle {\n public static long[][] buildPascal(int n) {\n long[][] dp = new long[n + 1][];\n for (int i = 0; i <= n; i++) {\n dp[i] = new long[i + 1];\n dp[i][0] = 1;\n dp[i][i] = 1;\n for (int j = 1; j < i; j++) {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n return dp;\n }\n\n // Usage: dp[n][r] gives C(n, r)\n}\n```\n\n```python\ndef build_pascal(n: int) -> list[list[int]]:\n dp = [[1] * (i + 1) for i in range(n + 1)]\n for i in range(2, n + 1):\n for j in range(1, i):\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]\n return dp\n\n# Usage: dp[n][r] gives C(n, r)\n```\n\n```cpp\nvector> buildPascal(int n) {\n vector> dp(n + 1);\n for (int i = 0; i <= n; i++) {\n dp[i].resize(i + 1, 1);\n for (int j = 1; j < i; j++) {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n return dp;\n}\n```\n\n```go\npackage main\n\n// buildPascal builds Pascal's triangle up to row n.\n// Usage: dp[n][r] gives C(n, r)\nfunc buildPascal(n int) [][]int64 {\n\tdp := make([][]int64, n+1)\n\tfor i := 0; i <= n; i++ {\n\t\tdp[i] = make([]int64, i+1)\n\t\tdp[i][0] = 1\n\t\tdp[i][i] = 1\n\t\tfor j := 1; j < i; j++ {\n\t\t\tdp[i][j] = dp[i-1][j-1] + dp[i-1][j]\n\t\t}\n\t}\n\treturn dp\n}\n```\n\n```csharp\npublic class PascalTriangle {\n public static long[][] BuildPascal(int n) {\n long[][] dp = new long[n + 1][];\n for (int i = 0; i <= n; i++) {\n dp[i] = new long[i + 1];\n dp[i][0] = 1;\n dp[i][i] = 1;\n for (int j = 1; j < i; j++) {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n return dp;\n }\n}\n```\n\n```rust\npub struct PascalTriangle;\n\nimpl PascalTriangle {\n pub fn build_pascal(n: i32) -> Vec> {\n let n = n as usize;\n let mut dp = vec![Vec::::new(); n + 1];\n for i in 0..=n {\n dp[i] = vec![1; i + 1];\n for j in 1..i {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n dp\n }\n}\n\n// Usage: dp[n][r] gives C(n, r)\n```\n\n```javascript\nfunction buildPascal(n) {\n const dp = [];\n for (let i = 0; i <= n; i++) {\n dp[i] = new Array(i + 1).fill(1);\n for (let j = 1; j < i; j++) {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n return dp;\n}\n```\n\n```typescript\nfunction buildPascal(n: number): number[][] {\n const dp: number[][] = [];\n for (let i = 0; i <= n; i++) {\n dp[i] = new Array(i + 1).fill(1);\n for (let j = 1; j < i; j++) {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n return dp;\n}\n```\n\n\n---\n\n### Approach 3: nCr with Modular Arithmetic (Large Values)\n\nThis is the approach you need for competitive programming and most interview problems involving large n. It precomputes factorials and inverse factorials modulo a prime (10^9 + 7), allowing O(1) nCr queries after O(n) preprocessing.\n\n\n```java\npublic class ModCombinatorics {\n static final long MOD = 1_000_000_007;\n static long[] fact;\n static long[] invFact;\n\n // Call this once before any nCr queries\n public static void precompute(int n) {\n fact = new long[n + 1];\n invFact = new long[n + 1];\n fact[0] = 1;\n for (int i = 1; i <= n; i++) {\n fact[i] = fact[i - 1] * i % MOD;\n }\n invFact[n] = modPow(fact[n], MOD - 2, MOD);\n for (int i = n - 1; i >= 0; i--) {\n invFact[i] = invFact[i + 1] * (i + 1) % MOD;\n }\n }\n\n public static long nCr(int n, int r) {\n if (r < 0 || r > n) return 0;\n return fact[n] % MOD * invFact[r] % MOD * invFact[n - r] % MOD;\n }\n\n private static long modPow(long base, long exp, long mod) {\n long result = 1;\n base %= mod;\n while (exp > 0) {\n if ((exp & 1) == 1) {\n result = result * base % mod;\n }\n exp >>= 1;\n base = base * base % mod;\n }\n return result;\n }\n}\n```\n\n```python\nMOD = 10**9 + 7\n\ndef precompute(n: int):\n fact = [1] * (n + 1)\n for i in range(1, n + 1):\n fact[i] = fact[i - 1] * i % MOD\n\n inv_fact = [1] * (n + 1)\n inv_fact[n] = pow(fact[n], MOD - 2, MOD)\n for i in range(n - 1, -1, -1):\n inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD\n\n return fact, inv_fact\n\ndef nCr(n: int, r: int, fact: list, inv_fact: list) -> int:\n if r < 0 or r > n:\n return 0\n return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD\n```\n\n```cpp\nconst long long MOD = 1e9 + 7;\nvector fact, invFact;\n\nlong long modPow(long long base, long long exp, long long mod) {\n long long result = 1;\n base %= mod;\n while (exp > 0) {\n if (exp & 1) result = result * base % mod;\n exp >>= 1;\n base = base * base % mod;\n }\n return result;\n}\n\nvoid precompute(int n) {\n fact.resize(n + 1);\n invFact.resize(n + 1);\n fact[0] = 1;\n for (int i = 1; i <= n; i++) {\n fact[i] = fact[i - 1] * i % MOD;\n }\n invFact[n] = modPow(fact[n], MOD - 2, MOD);\n for (int i = n - 1; i >= 0; i--) {\n invFact[i] = invFact[i + 1] * (i + 1) % MOD;\n }\n}\n\nlong long nCr(int n, int r) {\n if (r < 0 || r > n) return 0;\n return fact[n] % MOD * invFact[r] % MOD * invFact[n - r] % MOD;\n}\n```\n\n```go\npackage main\n\nconst MOD int64 = 1_000_000_007\n\nvar fact []int64\nvar invFact []int64\n\n// Call this once before any nCr queries\nfunc precompute(n int) {\n\tfact = make([]int64, n+1)\n\tinvFact = make([]int64, n+1)\n\tfact[0] = 1\n\tfor i := 1; i <= n; i++ {\n\t\tfact[i] = fact[i-1] * int64(i) % MOD\n\t}\n\tinvFact[n] = modPow(fact[n], MOD-2, MOD)\n\tfor i := n - 1; i >= 0; i-- {\n\t\tinvFact[i] = invFact[i+1] * int64(i+1) % MOD\n\t}\n}\n\nfunc nCr(n int, r int) int64 {\n\tif r < 0 || r > n {\n\t\treturn 0\n\t}\n\treturn fact[n] % MOD * invFact[r] % MOD * invFact[n-r] % MOD\n}\n\nfunc modPow(base int64, exp int64, mod int64) int64 {\n\tresult := int64(1)\n\tbase %= mod\n\tfor exp > 0 {\n\t\tif exp&1 == 1 {\n\t\t\tresult = result * base % mod\n\t\t}\n\t\texp >>= 1\n\t\tbase = base * base % mod\n\t}\n\treturn result\n}\n```\n\n```csharp\npublic class ModCombinatorics {\n const long MOD = 1_000_000_007;\n static long[] fact;\n static long[] invFact;\n\n public static void Precompute(int n) {\n fact = new long[n + 1];\n invFact = new long[n + 1];\n fact[0] = 1;\n for (int i = 1; i <= n; i++) {\n fact[i] = fact[i - 1] * i % MOD;\n }\n invFact[n] = ModPow(fact[n], MOD - 2, MOD);\n for (int i = n - 1; i >= 0; i--) {\n invFact[i] = invFact[i + 1] * (i + 1) % MOD;\n }\n }\n\n public static long NCr(int n, int r) {\n if (r < 0 || r > n) return 0;\n return fact[n] % MOD * invFact[r] % MOD * invFact[n - r] % MOD;\n }\n\n private static long ModPow(long b, long exp, long mod) {\n long result = 1;\n b %= mod;\n while (exp > 0) {\n if ((exp & 1) == 1) result = result * b % mod;\n exp >>= 1;\n b = b * b % mod;\n }\n return result;\n }\n}\n```\n\n```rust\nconst MOD: i64 = 1_000_000_007;\nstatic mut FACT: Vec = Vec::new();\nstatic mut INV_FACT: Vec = Vec::new();\n\n// Call this once before any nCr queries\npub fn precompute(n: usize) {\n let mut fact = vec![0i64; n + 1];\n let mut inv_fact = vec![0i64; n + 1];\n fact[0] = 1;\n for i in 1..=n {\n fact[i] = fact[i - 1] * i as i64 % MOD;\n }\n inv_fact[n] = mod_pow(fact[n], MOD - 2, MOD);\n for i in (0..n).rev() {\n inv_fact[i] = inv_fact[i + 1] * (i as i64 + 1) % MOD;\n }\n unsafe {\n FACT = fact;\n INV_FACT = inv_fact;\n }\n}\n\npub fn n_cr(n: usize, r: i32) -> i64 {\n if r < 0 || r as usize > n {\n return 0;\n }\n let r = r as usize;\n unsafe {\n FACT[n] % MOD * INV_FACT[r] % MOD * INV_FACT[n - r] % MOD\n }\n}\n\nfn mod_pow(mut base: i64, mut exp: i64, mod_: i64) -> i64 {\n let mut result = 1i64;\n base %= mod_;\n while exp > 0 {\n if exp & 1 == 1 {\n result = result * base % mod_;\n }\n exp >>= 1;\n base = base * base % mod_;\n }\n result\n}\n```\n\n```javascript\nconst MOD = 1_000_000_007n;\n\nfunction modPow(base, exp, mod) {\n let result = 1n;\n base %= mod;\n while (exp > 0n) {\n if (exp & 1n) result = result * base % mod;\n exp >>= 1n;\n base = base * base % mod;\n }\n return result;\n}\n\nfunction precompute(n) {\n const fact = new Array(n + 1);\n const invFact = new Array(n + 1);\n fact[0] = 1n;\n for (let i = 1; i <= n; i++) {\n fact[i] = fact[i - 1] * BigInt(i) % MOD;\n }\n invFact[n] = modPow(fact[n], MOD - 2n, MOD);\n for (let i = n - 1; i >= 0; i--) {\n invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;\n }\n return { fact, invFact };\n}\n\nfunction nCr(n, r, fact, invFact) {\n if (r < 0 || r > n) return 0n;\n return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;\n}\n```\n\n```typescript\nconst MOD = 1_000_000_007n;\n\nfunction modPow(base: bigint, exp: bigint, mod: bigint): bigint {\n let result = 1n;\n base %= mod;\n while (exp > 0n) {\n if (exp & 1n) result = result * base % mod;\n exp >>= 1n;\n base = base * base % mod;\n }\n return result;\n}\n\nfunction precompute(n: number): { fact: bigint[]; invFact: bigint[] } {\n const fact: bigint[] = new Array(n + 1);\n const invFact: bigint[] = new Array(n + 1);\n fact[0] = 1n;\n for (let i = 1; i <= n; i++) {\n fact[i] = fact[i - 1] * BigInt(i) % MOD;\n }\n invFact[n] = modPow(fact[n], MOD - 2n, MOD);\n for (let i = n - 1; i >= 0; i--) {\n invFact[i] = invFact[i + 1] * BigInt(i + 1) % MOD;\n }\n return { fact, invFact };\n}\n\nfunction nCr(n: number, r: number, fact: bigint[], invFact: bigint[]): bigint {\n if (r < 0 || r > n) return 0n;\n return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;\n}\n```\n\n\n---\n\n# Complexity Analysis\n\n\n| Approach | Time | Space | Best For |\n|----------|------|-------|----------|\n| Factorial-based nCr | O(r) per query | O(1) | Small n, single query |\n| Pascal's Triangle | O(n^2) build, O(1) query | O(n^2) | Multiple queries, small n |\n| Modular nCr (precomputed) | O(n) build + O(log p) for inverse, O(1) query | O(n) | Large n, mod arithmetic |\n\n\nFor most interview problems, the modular approach is what you need. Precompute once, query in O(1). The Pascal's Triangle approach is great when n is small (say, under 1000) and you want to avoid dealing with modular inverse.\n\n---\n\n# Applications in Counting Problems\n\nHere is a quick reference of how combinatorics maps to common problem types:\n\n\n| Problem | Combinatorial Formula |\n|---------|----------------------|\n| Subsets of size k from n elements | C(n, k) |\n| Total subsets of n elements | 2^n |\n| Grid paths (m x n, only right/down) | C(m+n-2, m-1) |\n| Distribute n identical items into k bins | C(n+k-1, k-1) |\n| Arrange n items with duplicates (a of type 1, b of type 2, ...) | n! / (a! * b! * ...) |\n| Choose and arrange r from n | P(n, r) = n! / (n-r)! |\n| Catalan number (balanced parentheses, BSTs) | C(2n, n) / (n+1) |\n\n\n\n```mermaid\nflowchart TD\n P[\"Counting Problem\"]:::primary\n P --> S{\"What are
we counting?\"}:::orange\n S --> A[\"Subsets\"]:::teal\n S --> B[\"Arrangements\"]:::teal\n S --> C[\"Distributions\"]:::teal\n S --> D[\"Paths\"]:::teal\n\n A --> A1[\"C(n, k) or 2^n\"]:::green\n B --> B1[\"P(n, r) or
n! / (a! * b!)\"]:::green\n C --> C1[\"Stars and bars:
C(n+k-1, k-1)\"]:::green\n D --> D1[\"Grid: C(m+n-2, m-1)
Catalan: C(2n,n)/(n+1)\"]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n","pageType":"dsa"}

Combinatorics

Get Premium