Skip to content

Binomial Coefficients & Catalan Numbers

Binomial coefficients

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!}, \quad 0 \le k \le n \]

Pascal’s triangle (DP): \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) with base \(\binom{n}{0}=\binom{n}{n}=1\).

Mod prime \(p\): precompute factorials and inverse factorials up to \(n\) modulo \(p\), then \(\binom{n}{k} = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \pmod{p}\). For non-prime moduli, use Lucas theorem when \(p\) is prime and \(n,k\) in base \(p\), or multi-prime CRT.

// modInv and fact[] precomputed for prime mod
long long binom(int n, int k, long long mod, const vector<long long>& fact,
                const vector<long long>& invfact) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invfact[k] % mod * invfact[n - k] % mod;
}

Catalan numbers

\[ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1} \]

Count valid parenthesis strings, binary trees, non-crossing partitions, etc.