Pattern Reference
Combinatorics
"Permutations, combinations, stars and bars, inclusion-exclusion, generating functions."
Loading...
Deep Dive Tutorial
Combinatorics problems ask "how many ways to arrange/choose/partition?" The brute force (enumerate all possibilities) always works but is exponential. The key is finding the formula. Once you recognize the structure — permutation, combination, partition, or arrangement with constraints — the formula follows directly.
Core Formulas
nPr and nCr
// nPr = n! / (n-r)! — ordered selection
// nCr = n! / (r! * (n-r)!) — unordered selection
// Pascal's triangle (small n, no mod needed)
function nCr_pascal(n, r) {
const C = Array.from({length: n+1}, () => new Array(n+1).fill(0));
for (let i = 0; i <= n; i++) {
C[i][0] = 1;
for (let j = 1; j <= i; j++)
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
return C[n][r];
}
// nCr mod p — precomputed factorials (large n)
const MOD = 1_000_000_007n;
const MAX = 200001;
const fact = new Array(MAX), inv_fact = new Array(MAX);
function precompute() {
fact[0] = 1n;
for (let i = 1; i < MAX; i++) fact[i] = fact[i-1] * BigInt(i) % MOD;
const powMod = (b, e) => { let r = 1n; b %= MOD; for (; e > 0n; e >>= 1n) { if (e & 1n) r = r * b % MOD; b = b * b % MOD; } return r; };
inv_fact[MAX-1] = powMod(fact[MAX-1], MOD - 2n);
for (let i = MAX-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * BigInt(i+1) % MOD;
}
function C(n, r) {
if (r < 0 || r > n) return 0n;
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}| Pattern | Formula | When |
|---|---|---|
| Choose r from n (unordered) | nCr = n! / (r!(n-r)!) | Subsets, combinations |
| Arrange r from n (ordered) | nPr = n! / (n-r)! | Permutations |
| All arrangements of n | n! | Derangements, full permutations |
| With repetition allowed | n^r | Each slot has n choices |
| Distribute n identical into k boxes | (n+k-1)Cr(k-1) | Stars and bars |
| At least one in each box | (n-1)Cr(k-1) | Stars and bars with constraint |
| Binary strings with exactly k ones | nCr(k) | Grid paths, binary arrangements |
Catalan Numbers
lightbulb
Catalan number C(n) = (2n choose n) / (n+1)
Appears in: valid parentheses sequences, BST count, triangulations, mountain ranges, ballot problem.
Recurrence: C(0)=1, C(n+1) = Σ C(i)×C(n-i) for i=0..n
Formula: C(n) = (2n)! / ((n+1)! × n!)
Appears in: valid parentheses sequences, BST count, triangulations, mountain ranges, ballot problem.
Recurrence: C(0)=1, C(n+1) = Σ C(i)×C(n-i) for i=0..n
Formula: C(n) = (2n)! / ((n+1)! × n!)
Catalan numbers (iterative)
// C(n) = C(2n, n) / (n+1)
function catalan(n) {
// Using the recurrence: C(n) = sum of C(i)*C(n-1-i)
const dp = new Array(n+1).fill(0n);
dp[0] = dp[1] = 1n;
for (let i = 2; i <= n; i++)
for (let j = 0; j < i; j++)
dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % MOD;
return dp[n];
}
// Or using formula: C(2n,n) / (n+1)
function catalan_formula(n) {
return C(2*n, n) * powMod(BigInt(n+1), MOD-2n, MOD) % MOD;
}Inclusion-Exclusion Principle
key
|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
General: alternately add/subtract intersections of size 1, 2, 3...
|A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
General: alternately add/subtract intersections of size 1, 2, 3...
Worked Problems
More Worked Problems
brain
Counting pattern recognition:
- "How many ways to arrange n distinct items?" → n!
- "How many ways to choose k from n?" → nCr
- "How many ways to fill k slots where each has n choices?" → n^k
- "Distribute n identical items into k distinct bins?" → stars-and-bars: C(n+k-1, k-1)
- "Count valid sequences of length n?" → often DP: dp[i] = ways to build prefix of length i
- "Count by inclusion-exclusion?" → |A∪B| = |A|+|B|-|A∩B|, generalize with Möbius
- Large n with mod? → precompute factorials and modular inverses
- "How many ways to arrange n distinct items?" → n!
- "How many ways to choose k from n?" → nCr
- "How many ways to fill k slots where each has n choices?" → n^k
- "Distribute n identical items into k distinct bins?" → stars-and-bars: C(n+k-1, k-1)
- "Count valid sequences of length n?" → often DP: dp[i] = ways to build prefix of length i
- "Count by inclusion-exclusion?" → |A∪B| = |A|+|B|-|A∩B|, generalize with Möbius
- Large n with mod? → precompute factorials and modular inverses