Combinatorics Basics

AL-10 | The counting foundations: product/sum rules, permutations and combinations, binomial coefficients with factorial / inverse-factorial precompute, and Stars and Bars. Appears in nearly every Codeforces Div 2 C-D tagged combinatorics or math.

Difficulty: [Intermediate]Prerequisites: Math Fundamentals, Number TheoryCF Rating Range: 1400-1900

Scope. This file is the foundations chapter. Catalan numbers and the inclusion-exclusion principle have their own dedicated files — 05-catalan-numbers.md and 06-inclusion-exclusion.md. Pattern boxes below cross-link to them where they appear naturally; do not expect the deep treatment here.

---

Quick Revisit

• USE WHEN: counting arrangements, selections, or distributions modulo a prime
• INVARIANT: C(n,k) = C(n-1,k-1) + C(n-1,k) (Pascal's recurrence)
• TIME: O(n) precompute factorials, O(1) per C(n,k) query | SPACE: O(n)
• CLASSIC BUG: forgetting inverse factorials -- C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k] mod p
• PRACTICE: see practice problems in this chapter

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

Count the number of paths in a 4x3 grid from the top-left corner to the bottom-right corner, moving only right or down.

The grid has 4 columns and 3 rows, so you must take 3 right-moves and 2 down-moves (for a total of 5 moves).

Naive approach: enumerate every possible path by hand.

Start (0,0) --> Goal (3,2)

Path 1:  R R R D D
Path 2:  R R D R D
Path 3:  R R D D R
Path 4:  R D R R D
Path 5:  R D R D R
Path 6:  R D D R R
Path 7:  D R R R D
Path 8:  D R R D R
Path 9:  D R D R R
Path 10: D D R R R

Even at this tiny size you have to carefully list all 10 and hope you missed none. For a 20x15 grid the number of paths is astronomical. Enumeration does not scale.

Every path from $(0,0)$ to $(m-1,n-1)$ is a sequence of exactly $(m-1)$ R-moves and $(n-1)$ D-moves -- choosing which positions in the sequence are R-moves gives $(\genfrac{}{}{0ex}{}{(m-1)+(n-1)}{m-1})$.

Think of it like ordering from a fixed-length menu. You have 5 slots in your order (the 5 moves). You must fill exactly 3 of them with "R" and 2 with "D". The number of ways to choose which 3 slots get "R" is $(\genfrac{}{}{0ex}{}{5}{3})=10$.

This works because:

• Every path has the same length: $(m-1)+(n-1)$ moves total.
• The path is completely determined by which moves are R (the rest are D).
• No two different choices of positions produce the same path.

The insight breaks when the grid has blocked cells, weighted edges, or diagonal moves -- then you need DP or inclusion-exclusion instead of a single binomial coefficient.

Visual Walkthrough — verifying Pascal's recurrence on the grid

The grid-filling DP below is doing exactly Pascal's triangle in disguise: each cell $(r,c)$ counts $(\genfrac{}{}{0ex}{}{r+c}{c})$, and the recurrence $\text{paths}(r,c)=\text{paths}(r-1,c)+\text{paths}(r,c-1)$ is $(\genfrac{}{}{0ex}{}{r+c}{c})=(\genfrac{}{}{0ex}{}{r+c-1}{c-1})+(\genfrac{}{}{0ex}{}{r+c-1}{c})$. The table is here not because we drifted into DP, but because seeing the recurrence on a grid is the cleanest way to prove that $(\genfrac{}{}{0ex}{}{n}{k})$ counts paths.

Fill each cell with the number of distinct paths from $(0,0)$ to that cell.

Step 1. The top row and left column each have exactly one path (all R or all D respectively). Seed them with 1.

  col  0   1   2   3
row
 0  [  1   1   1   1 ]
 1  [  1   .   .   . ]
 2  [  1   .   .   . ]

Step 2. Cell $(1,1)$: the only ways to arrive are from above $(0,1)$ or from the left $(1,0)$. So $\text{paths}(1,1)=1+1=2$.

  col  0   1   2   3
row
 0  [  1   1   1   1 ]
 1  [  1  *2*  .   . ]
 2  [  1   .   .   . ]

Step 3. Fill the rest of row 1 and cell $(2,1)$ the same way.

  col  0   1   2   3
row
 0  [  1   1   1   1 ]
 1  [  1   2   3   4 ]
 2  [  1  *3*  .   . ]

Cell $(1,2)=1+2=3$. Cell $(1,3)=1+3=4$. Cell $(2,1)=1+2=3$.

Step 4. Complete row 2.

  col  0   1   2   3
row
 0  [  1   1   1   1 ]
 1  [  1   2   3   4 ]
 2  [  1   3   6  *10*]

Cell $(2,2)=3+3=6$. Cell $(2,3)=4+6=\mathbf{10}$.

The answer is 10. This matches $(\genfrac{}{}{0ex}{}{5}{3})=(\genfrac{}{}{0ex}{}{5}{2})=10$.

Operation count: we computed one addition per interior cell, so $(m-1)\times (n-1)=3\times 2=6$ additions total. For a general grid this is $O(m\cdot n)$, which is also the cost of building Pascal's triangle up to row $m+n$.

The Invariant

+----------------------------------------------------------+
| INVARIANT: C(n,k) = C(n-1,k-1) + C(n-1,k). Every entry  |
| is built from exactly two entries in the previous row.    |
+----------------------------------------------------------+

Invariant. $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$, and each cell in Pascal's triangle counts the number of paths from the apex to that position.

Connection to the walkthrough: the grid-filling recurrence $\text{paths}(r,c)=\text{paths}(r-1,c)+\text{paths}(r,c-1)$ is exactly Pascal's recurrence with the substitution $n=r+c$, $k=c$.

Row $n$ of Pascal's triangle:

  n=0:             1
  n=1:           1   1
  n=2:         1   2   1
  n=3:       1   3   3   1
  n=4:     1   4   6   4   1
  n=5:   1   5  10  10   5   1

  Entry at position k in row n = C(n, k)

  Recurrence shown:
      C(4,2) + C(4,3) = C(5,3)
         6   +   4    =   10

Each row sums to $2^n$, and the triangle encodes binomial expansions:

PASCAL'S TRIANGLE -- symmetry and row sums:

  Row 0:                 1                    sum = 1  = 2^0
  Row 1:               1   1                  sum = 2  = 2^1
  Row 2:             1   2   1                sum = 4  = 2^2
  Row 3:           1   3   3   1              sum = 8  = 2^3
  Row 4:         1   4   6   4   1            sum = 16 = 2^4
  Row 5:       1   5  10  10   5   1          sum = 32 = 2^5
  Row 6:     1   6  15  20  15   6   1        sum = 64 = 2^6

  Symmetry: C(n, k) = C(n, n-k)   (read each row forward or backward)
  Hockey stick: sum of a diagonal = entry below-right of the last term
     C(2,0) + C(3,0) + C(4,0) + C(5,0) = C(6,1)
       1    +   1    +   1    +   1     =   4  ??? 
     Actually: C(0,0)+C(1,0)+C(2,0)+C(3,0)+C(4,0) = C(5,1) = 5

The value 10 at row 5, position 3 is the same 10 we computed in the grid: $(\genfrac{}{}{0ex}{}{5}{3})$ paths from $(0,0)$ to $(3,2)$.

What the Code Won't Teach You

The code gives you C(n, k) in $O(1)$ -- but it won't teach you when to call it. The hardest part of combinatorics is modeling: translating a story problem into "I am choosing $k$ items from $n$." The formula is 5% of the work; recognizing which formula applies is 95%.

MODELING DECISION TREE:

  "How many ways to..."
       │
       ├─ choose k items from n? ──────────-> C(n, k)
       │
       ├─ distribute n identical            ┌─ each bin >= 0? -> C(n+k-1, k-1)
       │   items into k bins? ──────────────┤
       │                                    └─ each bin >= 1? -> C(n-1, k-1)
       │
       ├─ arrange items with              multinomial:
       │   repeated types? ──────────────->  n! / (k₁! * k₂! * ... * kₘ!)
       │
       ├─ avoid certain positions? ───────-> PIE or derangements
       │
       └─ count balanced structures? ─────-> Catalan

The code also hides the why behind inverse factorials. The backward propagation trick inv_fac[i] = inv_fac[i+1] * (i+1) % MOD works because $(i!{)}^{-1}=((i+1)!{)}^{-1}\cdot (i+1)$. If you don't see this identity, the precomputation is cargo-cult code -- you can't debug it when something goes wrong.

When to Reach for This

Trigger phrases in problem statements:

• "choose $k$ from $n$" or "select a subset of size $k$" --> $(\genfrac{}{}{0ex}{}{n}{k})$.
• "count arrangements", "number of distinct sequences" with fixed symbol counts --> multinomial or binomial.
• "answer modulo ${10}^9+7$" with tag combinatorics --> precompute factorials and inverse factorials for $O(1)$ binomial queries.
• "grid paths", "lattice paths" (right/down only) --> $(\genfrac{}{}{0ex}{}{n+m}{n})$.
• "distribute identical objects into bins" --> Stars and Bars.

Counter-examples (looks like combinatorics but is not):

• "shortest path in weighted grid" --> Dijkstra / BFS, not counting.
• "count subsequences of arbitrary length" --> usually DP, not a closed-form binomial.
• "permutations with complex forbidden patterns" --> may need PIE or DP, not a single $(\genfrac{}{}{0ex}{}{n}{k})$.
• Constraints with $n\le {10}^{18}$ and no prime modulus --> Lucas' theorem or a completely different approach; naive factorial precomputation is impossible.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
__int128	built-in	128-bit integer for intermediate products that overflow long long.	--
gcd(a, b)	<numeric>	Greatest common divisor (C++17). Needed for simplifying fractions in combinatorial formulas.	$O(\log min(a,b))$
bitset<N>	<bitset>	Compact bitmask. Use for PIE subset enumeration when $N$ is fixed at compile time.	$O(N/64)$ per op
__builtin_popcountll(x)	built-in	Count set bits in unsigned long long. Used to determine PIE sign from subset parity.	$O(1)$
vector<vector<ll>>	<vector>	2D array for Pascal's triangle DP when $n\le 5000$.	--
accumulate(b, e, init)	<numeric>	Sum a range. Useful for summing PIE terms.	$O(n)$

---

Implementation (Contest-Ready)

Version 1: nCk mod p -- Minimal Contest Template

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;

ll fac[MAXN], inv_fac[MAXN];

ll power(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

void precompute() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv_fac[MAXN - 1] = power(fac[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();

    int n, k;
    cin >> n >> k;
    cout << C(n, k) << "\n";
}

Version 2: Explained with Comments + Inclusion-Exclusion Template

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;

ll fac[MAXN], inv_fac[MAXN];

// Binary exponentiation: computes a^b mod m.
// Used once to bootstrap inverse factorials.
ll power(ll a, ll b, ll mod) {
    ll res = 1;
    a %= mod;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

// Precompute factorial and inverse factorial arrays.
// Key insight: only ONE modular inverse (via Fermat) is needed.
// inv_fac[i] = inv_fac[i+1] * (i+1) because (i!)^{-1} = ((i+1)!)^{-1} * (i+1).
void precompute() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % MOD;

    // Single expensive call: inverse of (MAXN-1)!
    inv_fac[MAXN - 1] = power(fac[MAXN - 1], MOD - 2, MOD);

    // Propagate backwards: inv_fac[i] = inv_fac[i+1] * (i+1) mod p
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

// C(n, k) mod p in O(1). Returns 0 for invalid inputs.
ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

// Catalan number: C_n = C(2n, n) / (n + 1) = C(2n, n) - C(2n, n+1)
ll catalan(int n) {
    return (C(2 * n, n) - C(2 * n, n + 1) + MOD) % MOD;
}

// --- Inclusion-Exclusion over bitmask ---
// Given m "bad" properties, computes the count of elements satisfying NONE.
// f(mask) returns the count of elements satisfying ALL properties in mask.
// Example: derangements, surjections, coprime counting.
//
// Result = sum over all subsets S of (-1)^|S| * f(S)
//        = f({}) - sum|S|=1 f(S) + sum|S|=2 f(S) - ...
//
// Requires m <= 20 (2^m subsets).
template<typename F>
ll inclusion_exclusion(int m, F&& f) {
    ll ans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        ll val = f(mask);
        // __builtin_popcount gives |S|; odd |S| -> subtract
        if (__builtin_popcount(mask) % 2 == 0)
            ans = (ans + val) % MOD;
        else
            ans = (ans - val + MOD) % MOD;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute();

    // Example: count derangements of n elements using PIE.
    // A derangement is a permutation with no fixed point.
    // Let A_i = {permutations where position i is fixed}.
    // |A_i1 ^ A_i2 ^ ... ^ A_ik| = (n - k)! (fix k positions, permute rest).
    // There are C(n, k) ways to choose which k are fixed.
    // D(n) = sum_{k=0}^{n} (-1)^k * C(n,k) * (n-k)!
    int n;
    cin >> n;

    // PIE approach (direct formula):
    ll derangements = 0;
    for (int k = 0; k <= n; k++) {
        ll term = C(n, k) * fac[n - k] % MOD;
        if (k % 2 == 0)
            derangements = (derangements + term) % MOD;
        else
            derangements = (derangements - term + MOD) % MOD;
    }
    cout << derangements << "\n";

    // Alternative: using the inclusion_exclusion template with m small properties.
    // Suppose m = number of prime divisors of some N, count integers in [1..N]
    // coprime to N.
    // This is Euler's totient, but demonstrates the PIE template.
    int N = 30;
    vector<int> primes = {2, 3, 5}; // prime factors of 30
    int m = primes.size();

    ll coprime_count = inclusion_exclusion(m, [&](int mask) -> ll {
        // Product of primes in the mask
        ll prod = 1;
        for (int i = 0; i < m; i++)
            if (mask >> i & 1)
                prod *= primes[i];
        return N / prod; // count of multiples of prod in [1..N]
    });
    // coprime_count = 30 - 15 - 10 - 6 + 5 + 3 + 2 - 1 = 8 = phi(30)
    cout << coprime_count << "\n";
}

Bonus: Pascal's Triangle DP (when $n\le 5000$, no modular inverse needed)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MOD = 1e9 + 7;

// Build Pascal's triangle up to row n.
// C[i][j] = C(i, j) mod MOD.
vector<vector<ll>> pascal(int n) {
    vector<vector<ll>> C(n + 1, vector<ll>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
    return C;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto C = pascal(5000);
    cout << C[5000][2500] << "\n";
}

---

Operations Reference

Operation	Time	Space	Notes
Precompute factorials + inverse factorials	$O(n+\log p)$	$O(n)$	One-time setup. The $\log p$ is for the single power call.
$(\genfrac{}{}{0ex}{}{n}{k})modp$ (precomputed)	$O(1)$	--	After precomputation.
$(\genfrac{}{}{0ex}{}{n}{k})modp$ (no precompute)	$O(k\log p)$	$O(1)$	Multiply $k$ terms, each needing a modular inverse.
Pascal's triangle (build up to row $n$)	$O(n^2)$	$O(n^2)$	No modular inverse needed. Limited to $n\le 5000$.
Catalan number $C_n$ (precomputed)	$O(1)$	--	Just a binomial coefficient.
Inclusion-exclusion over $m$ properties	$O(2^m\cdot f)$	$O(1)$	$f$ = cost of evaluating one subset. $m\le 20$.
Stars and Bars	$O(1)$	--	Single binomial coefficient query.
Derangements (PIE formula)	$O(n)$	$O(1)$	$D(n)=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$

---

Problem Patterns & Tricks

Pattern 1: Direct Counting with $(\genfrac{}{}{0ex}{}{n}{k})$

The problem gives a set of size $n$ and asks how many ways to choose $k$ elements (possibly with constraints that reduce to a simple formula).

Approach: Identify what is being chosen. Translate constraints into a binomial coefficient. Precompute factorials.

answer = C(n, k)  or  product of several C(n_i, k_i)

Problems: CF 1462D - Add to Neighbour and Remove, CF 1312C - Adding Powers of Two

---

Pattern 2: Stars and Bars (Distributing Identical Objects)

"Distribute $n$ identical items into $k$ groups" or "count non-negative integer solutions to $x_1+\cdots +x_k=n$."

Approach: Direct Stars and Bars: $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$. If each $x_i\ge 1$, substitute $y_i=x_i-1$ to get $(\genfrac{}{}{0ex}{}{n-1}{k-1})$. If upper bounds exist, combine with PIE.

STARS AND BARS -- placing dividers among stars:

  Distribute n=5 identical stars into k=3 bins:

  Stars: * * * * *   Dividers: | |   (k-1 = 2 dividers)

  Arrangement:  * * | * | * *    ->  bins: [2, 1, 2]
                * * * | | * *    ->  bins: [3, 0, 2]
                | * * * * | *    ->  bins: [0, 4, 1]

  Total arrangements = C(n+k-1, k-1) = C(7, 2) = 21

  For "each bin >= 1": pre-place 1 star per bin (costs k stars),
  then distribute remaining n-k = 2 stars freely:
  C(n-1, k-1) = C(4, 2) = 6

PIE VENN DIAGRAM -- 3 properties:

     ┌─────────────────────────────────────┐
     │                 U (universe)         │
     │    ┌───────────┐                     │
     │    │     A      \                    │
     │    │   ┌────┐    \                   │
     │    │   │A∩B │  ┌──┐                  │
     │    │   │    │  │A∩│B│                │
     │    │   └──┬─┘  │B∩│ │                │
     │    │      │A∩B │C │ │                │
     │    └──────┤∩C  ├──┘ │                │
     │           └────┘  C │                │
     │                └────┘                │
     └─────────────────────────────────────┘

  |A ∪ B ∪ C| = |A| + |B| + |C|
              - |A∩B| - |A∩C| - |B∩C|
              + |A∩B∩C|

  "None of A,B,C" = |U| - |A∪B∪C|

// Non-negative: C(n + k - 1, k - 1)
// Positive:     C(n - 1, k - 1)

Problems: CF 1288C - Two Arrays, CF 1081C - Colorful Bricks

---

Pattern 3: Inclusion-Exclusion on Bitmask

"Count elements satisfying NONE of $m$ bad conditions" where $m$ is small ($\le 20$).

Approach: For each subset $S$ of conditions, compute how many elements violate all conditions in $S$ simultaneously. Alternate signs by $|S|$.

ll ans = 0;
for (int mask = 0; mask < (1 << m); mask++) {
    ll val = count_satisfying_all(mask);
    if (__builtin_popcount(mask) % 2 == 0)
        ans = (ans + val) % MOD;
    else
        ans = (ans - val + MOD) % MOD;
}

Problems: CF 1559D2 - Mocha and Diana (Hard), CF 451E - Devu and Flowers

---

Pattern 4: Derangements

"Count permutations with no fixed points" or similar constraint on forbidden positions.

Approach: $D(n)=(n-1)(D(n-1)+D(n-2))$ with $D(0)=1,D(1)=0$. Or PIE: $D(n)=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!$. Approximation: $D(n)\approx n!/e$.

Problems: CF 888D - Almost Identity Permutations

---

Pattern 5: Catalan Number Variants

Problem counts one of: valid bracket sequences of length $2n$, binary trees with $n$ internal nodes, monotonic grid paths below the diagonal, triangulations of a convex $(n+2)$-gon.

Approach: Recognize the Catalan structure. $C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$. Use the subtraction form $C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1})$ to avoid division.

ll catalan(int n) {
    return (C(2*n, n) - C(2*n, n+1) + MOD) % MOD;
}

Problems: CF 1264D - Beautiful Bracket Sequence, CF 1830C - Hyperregular Bracket Strings

---

Pattern 6: Counting Paths on a Grid

"How many ways to go from $(0,0)$ to $(n,m)$ moving only right or down?"

Approach: Total steps $=n+m$, choose $n$ of them to be "down" (or $m$ to be "right"): answer is $(\genfrac{}{}{0ex}{}{n+m}{n})$. With forbidden cells, use DP or PIE over the forbidden points.

answer = C(n + m, n)

Problems: CF 559C - Gerald and Giant Chess, CF 722E - Research Rover

---

Pattern 7: Multinomial / Product of Binomials

"How many distinct strings can be formed from given characters?" or "distribute items into multiple labeled groups of specified sizes."

Approach: $\frac{n!}{k_1!\cdot k_2!\cdots k_m!}=(\genfrac{}{}{0ex}{}{n}{k_1})(\genfrac{}{}{0ex}{}{n-k_1}{k_2})\cdots$ Compute as a product of binomial coefficients, or directly as fac[n] * inv_fac[k1] * ... * inv_fac[km] % MOD.

Problems: CF 1461D - Divide and Summarize, CF 1475D - Cleaning the Phone

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|              COMBINATORICS BASICS CHEAT SHEET                |
+--------------------------------------------------------------+
| SETUP (paste at top of solution):                            |
|   ll fac[MAXN], inv_fac[MAXN];                               |
|   // precompute() in main before queries                     |
+--------------------------------------------------------------+
| FORMULAS:                                                    |
|   C(n,k) = fac[n] * inv_fac[k] % MOD * inv_fac[n-k] % MOD  |
|   Stars&Bars: C(n+k-1, k-1)   [non-neg solutions]          |
|   Catalan:    C(2n,n) - C(2n, n+1)                          |
|   Derange:    D(n) = (n-1)*(D(n-1) + D(n-2))                |
+--------------------------------------------------------------+
| PIE (m <= 20):                                               |
|   for mask in 0..2^m-1:                                      |
|     sign = (-1)^popcount(mask)                               |
|     ans += sign * f(mask)                                    |
+--------------------------------------------------------------+
| WATCH OUT:                                                   |
|   - C(n,k) = 0 when k<0 or k>n                              |
|   - 1LL * a * b % MOD  (avoid int overflow)                  |
|   - inv_fac via backward propagation (1 pow call total)      |
|   - Stars&Bars "at least 1" = C(n-1, k-1)                   |
+--------------------------------------------------------------+
| COMPLEXITY:                                                  |
|   Precompute: O(n)   |   Query C(n,k): O(1)                 |
|   Pascal DP:  O(n^2) |   PIE: O(2^m * f)                    |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Mental Traps

"I know the formula, I just plug in numbers." Combinatorics problems almost never say "compute $(\genfrac{}{}{0ex}{}{n}{k})$." They describe a scenario. Your job is to model it -- what are you choosing? Are choices independent? Is there overcounting? The formula is the easy part; wrong modeling causes 90% of WAs.

TRAP: Stars and Bars variants look identical but differ by 1

  "distribute 10 candies among 3 kids"
     ├─ "each gets >= 0"  -> C(10+3-1, 3-1) = C(12, 2) = 66
     └─ "each gets >= 1"  -> C(10-1, 3-1)   = C(9, 2)  = 36

  ONE WORD changes the answer by almost 2x!

"PIE is just alternating signs -- I can write it from memory." The sign pattern is easy. The hard part is computing $f(\text{mask})$ -- the count of elements satisfying ALL properties in the mask simultaneously. Getting $f$ wrong invalidates the entire PIE. Always verify $f(\mathrm{\varnothing })$ equals the total unrestricted count.

"Negative mod won't bite me -- I've seen the +MOD trick." You've seen it, but you'll forget it under contest pressure. The expression (a - b) % MOD is negative in C++ when a < b. Write (a - b % MOD + MOD) % MOD every single time -- make it a reflex, not a decision.

SIGN ERROR TRAP:

  a = 3, b = 7, MOD = 5
  
  WRONG:  (3 - 7) % 5  = -4 % 5  = -4  (C++ behavior!)
  RIGHT:  (3 - 7 % 5 + 5) % 5 = (3 - 2 + 5) % 5 = 6 % 5 = 1

• Overflow in multiplication chain. fac[n] * inv_fac[k] * inv_fac[n-k] % MOD is wrong -- the first multiply overflows long long before the mod. Write fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n-k] % MOD or chain with intermediate % MOD.

• MAXN too small. If the problem has $n$ up to $2\times {10}^6$, you need MAXN = 2e6 + 5, not 1e6 + 5. Off-by-one here gives wrong answers or segfaults.

• Forgetting precompute(). Easy to forget in contest stress. Put it as the first line in main().

• $(\genfrac{}{}{0ex}{}{n}{k})$ with $k>n$ or $k<0$. Must return $0$, not crash. Always guard in your C() function.

• Negative mod result. (a - b) % MOD can be negative in C++. Always add MOD before taking mod: (a - b % MOD + MOD) % MOD.

• Stars and Bars off-by-one. "At least 0 per bin" uses $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$. "At least 1 per bin" uses $(\genfrac{}{}{0ex}{}{n-1}{k-1})$. Mixing these up is the #1 mistake.

• PIE sign error. Empty set ($|S|=0$) contributes $+f(\mathrm{\varnothing })$, which is the total count without restrictions. Subset of size 1 gets $-$. Double-check with a small example.

• Pascal's triangle memory. A $5000\times 5000$ long long array is $\sim 200$ MB -- use int and cast to long long only during addition, or use 1D rolling array if you only need one row.

• Catalan: integer division trap. $C_n=(\genfrac{}{}{0ex}{}{2n}{n})/(n+1)$ requires modular inverse of $(n+1)$. Safer: use $C_n=(\genfrac{}{}{0ex}{}{2n}{n})-(\genfrac{}{}{0ex}{}{2n}{n+1})$ which avoids division entirely.

• Debugging PIE. Print the contribution of each bitmask. Verify against brute-force for $n\le 10$.

---

Common Mistakes

1. Not precomputing inverse factorials. C(n,k) mod p needs fact[n] * inv_fact[k] % p * inv_fact[n-k] % p. Computing the inverse on-the-fly for each query is too slow.
2. Stars and Bars off-by-one. Distributing n identical items into k distinct bins = C(n+k-1, k-1). Using C(n+k, k) or C(n+k-1, n) instead gives the wrong formula.
3. Inclusion-exclusion sign errors. The sign alternates with subset size: + for even, - for odd. A single sign flip invalidates the entire computation.
4. Overflow in Pascal's triangle. C(n,k) grows fast. If not working modulo p, values overflow long long for n > ~60.
5. Forgetting the "at least 0" constraint. Stars and Bars counts non-negative distributions. For "at least 1 per bin," substitute n' = n - k first.
6. Sizing factorial tables to the input, not the formula. On "Distributing Apples" ($n$ apples, $k$ children, answer $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$) with $n,k\le {10}^6$, precomputing factorials only up to $n$ RTEs out of bounds on any test where the formula dereferences fact[n + k - 1] at index near $2\times {10}^6$. Always trace your formula to find the maximum argument to $C(\cdot ,\cdot )$ and size the table to that. For Stars and Bars it is $n+k$, not just $n$.

Debug Drills

Drill 1. Inverse factorial computed wrong.

inv_fact[0] = 1;
for (int i = 1; i <= N; i++)
    inv_fact[i] = power(fact[i], MOD - 2, MOD);  // What's the issue?

What's wrong?

This is correct but O(N log MOD) -- computing N modular exponentiations. The fast way: compute inv_fact[N] = power(fact[N], MOD-2, MOD) once, then inv_fact[i] = inv_fact[i+1] * (i+1) % MOD backwards. This is O(N) + one exponentiation.

Drill 2. C(n, k) returns garbage for edge cases.

long long C(int n, int k) {
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}
// Called with C(5, 7). What happens?

What's wrong?

When k > n, n - k is negative, causing an out-of-bounds array access (or wrapping to a huge index). Add a guard: if (k < 0 || k > n) return 0;

Drill 3. Stars and Bars off-by-one.

// n identical balls into k distinct boxes, each box >= 0
long long stars_and_bars(int n, int k) {
    return C(n + k, k);  // What's wrong?
}

What's wrong?

The correct formula is C(n + k - 1, k - 1). The - 1 comes from choosing positions for k - 1 dividers among n + k - 1 slots. Off-by-one here gives a systematically wrong answer.

---

Self-Test

Before moving to practice problems, verify you can do each of these without looking at the notes above:

• [ ] Write precompute() and C(n, k) from memory, including backward propagation for inv_fac[]
• [ ] State Stars and Bars for both variants (>= 0 and >= 1) and derive one from the other
• [ ] Compute $D(4)=9$ (derangements of 4 elements) by hand using PIE
• [ ] Write the inclusion-exclusion bitmask loop with correct sign handling
• [ ] Explain why fac[n] * inv_fac[k] * inv_fac[n-k] % MOD overflows but fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n-k] % MOD doesn't
• [ ] Given "distribute 7 identical balls into 4 distinct boxes, each box gets >= 2," reduce to Stars and Bars

---

Practice Problems

Rating	You should be able to...
CF 1200	Compute C(n, k) using Pascal's triangle for small n
CF 1500	Precompute factorial and inverse factorial arrays; evaluate C(n, k) mod p in O(1)
CF 1800	Apply Stars and Bars with upper-bound constraints (PIE); count lattice paths with obstacles
CF 2100	Combine multinomial coefficients with generating functions; solve complex counting with DP + combinatorics

#	Problem	Source	Difficulty	Key Idea
1	Quasi Binary	CF 538B	Easy (1400)	Basic counting / representation
2	Two Arrays	CF 1288C	Easy (1600)	Stars and Bars
3	Colorful Bricks	CF 1081C	Easy (1500)	Binomial coefficient
4	Almost Identity Permutations	CF 888D	Medium (1600)	Derangement counting
5	Gerald and Giant Chess	CF 559C	Medium (1900)	Grid paths + PIE
6	Devu and Flowers	CF 451E	Medium (1900)	Stars and Bars + PIE with upper bounds
7	Beautiful Bracket Sequence	CF 1264D	Hard (2100)	Catalan / bracket counting
8	Hyperregular Bracket Strings	CF 1830C	Hard (2100)	Catalan over subsets
9	Binomial Coefficients	CSES	1400	Precompute factorials and inverse factorials
10	Creating Strings II	CSES	1500	Multinomial coefficient -- n! / (c1! * c2! * ...)
11	Distributing Apples	CSES	1500	Stars and bars: C(n+k-1, k-1)
12	Bracket Sequences I	CSES	1700	Catalan number application

---

Further Reading

• cp-algorithms: Binomial Coefficients -- Complete reference with all computation methods.
• cp-algorithms: Catalan Numbers -- Derivation, applications, and generalizations.
• cp-algorithms: Inclusion-Exclusion -- Detailed treatment with worked examples.
• CF Blog: Combinatorics tutorial by pikmike -- Problem-focused, competition-oriented.
• CF Blog: Modular Arithmetic for Beginners -- Covers modular inverse, precomputation tricks.

Cross-references in this notebook:

• See: Number Theory -- modular inverse, Fermat's theorem (used for factorial precomputation).

---

Recap

• Precompute fact[] and inv_fact[] up to MAXN for O(1) binomial coefficient queries mod p.
• Stars and Bars: n identical items into k bins = C(n+k-1, k-1).
• Inclusion-exclusion: count |A_1 union ... union A_k| via alternating sum of intersection sizes.
• Pascal's recurrence is useful for small n or when you need the full triangle, but factorial-based computation is faster for individual queries.

---

Cross-Links

• Math Fundamentals -- modular exponentiation for computing inverse factorials
• Number Theory -- prime factorization feeds into combinatorial formulas
• Catalan Numbers -- a key combinatorial sequence built on binomial coefficients