Combinatorics

Permutations

P (n) = n! (arrange all n distinct objects)

P (n, r) = \frac{n !}{( n - r )!} (arrange r of n distinct objects, order matters)

Combinations

(r n) = \frac{n !}{r ! ( n - r )!} (choose r of n distinct objects, order doesn’t matter)

Also written $n C r$ .

Pascal’s identity:

(r n) = (r - 1 n - 1) + (r n - 1) .

Basis of Pascal’s triangle; gives an $O (n^{2})$ DP for binomial coefficients without factorials or modular inverses.

Identities:

(0 n) = (n n) = 1, (r n) = (n - r n), r = 0 \sum n (r n) = 2^{n} .

Binomial Theorem

(x + y)^{n} = r = 0 \sum n (r n) x^{n - r} y^{r} .

Computing nCr Fast, Modulo a Prime

For $n$ up to $1 0^{6}$ – $1 0^{7}$ : precompute factorials and inverse factorials mod $MOD$ , then answer each query in $O (1)$ . (See Modular Arithmetic for the standalone modinv / modpow building blocks.)

f a c t [0] = 1, f a c t [i] = f a c t [i - 1] \cdot i mod MOD .

in v f a c t [N] = f a c t [N]^{MOD - 2} mod MOD (Fermat’s Little Theorem), in v f a c t [i - 1] = in v f a c t [i] \cdot i mod MOD .

(r n) mod MOD = f a c t [n] \cdot in v f a c t [r] \cdot in v f a c t [n - r] mod MOD .

Code — Factorial / Inverse-Factorial Precomputation

#include <bits/stdc++.h>
using namespace std;
 
static const long long MOD = 1000000007;
static const int MAXN = 1000000;
 
long long fact[MAXN + 1], invfact[MAXN + 1];
 
long long modpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;
 
    invfact[MAXN] = modpow(fact[MAXN], MOD - 2, MOD);
    for (int i = MAXN; i > 0; i--)
        invfact[i - 1] = invfact[i] * i % MOD;
}
 
long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD;
}

Code — Pascal’s-Triangle DP (Small n, No Modular Inverse Needed)

vector<vector<long long>> pascal(int n, long long mod) {
    vector<vector<long long>> C(n + 1, vector<long long>(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;
}

Catalan Numbers

C_{n} = \frac{1}{n + 1} (n 2 n) = (n 2 n) - (n + 1 2 n), C_{0} = 1.

C_{n + 1} = i = 0 \sum n C_{i} C_{n - i} .

Mathematical Proof

The closed form is derived with the reflection principle: count lattice paths from $(0, 0)$ to $(n, n)$ using unit right/up steps that never cross above the diagonal. The total number of monotone paths is $(n 2 n)$ . Reflecting any “bad” path (one that touches the line $y = x + 1$ ) across that line maps it bijectively onto an unconstrained path to $(n - 1, n + 1)$ , of which there are $(n + 1 2 n)$ . Subtracting the bad paths leaves $(n 2 n) - (n + 1 2 n)$ valid paths, which simplifies to $\frac{1}{n + 1} (n 2 n)$ .

Catalan numbers count balanced parenthesizations, binary trees with $n$ internal nodes, Dyck paths, and polygon triangulations, among many other structures.

long long catalan(int n, long long mod) {
    // requires precompute() from the nCr section above
    return ((nCr(2 * n, n) - nCr(2 * n, n + 1)) % mod + mod) % mod;
}

Time Complexity: $O (1)$ per query (given precomputed factorials), $O (N)$ precompute

Stars and Bars

Number of ways to distribute $n$ identical items into $k$ distinguishable bins.

Empty bins allowed:

(k - 1 n + k - 1) .

Each bin non-empty:

(k - 1 n - 1) .

Mathematical Proof

Represent a distribution as a row of $n$ stars (items) separated by $k - 1$ bars (bin boundaries). Any arrangement of these $n + k - 1$ symbols is a valid distribution, and it’s fully determined by choosing which $k - 1$ of the $n + k - 1$ positions hold bars — hence $(k - 1 n + k - 1)$ . For the non-empty case, first place one item in every bin, then distribute the remaining $n - k$ items freely, giving $(k - 1 ( n - k ) + k - 1) = (k - 1 n - 1)$ .

long long distributeItems(int n, int k, bool allowEmpty) {
    if (allowEmpty) return nCr(n + k - 1, k - 1);
    return nCr(n - 1, k - 1); // n must be >= k
}

Inclusion-Exclusion Principle

i = 1 ⋃ n A_{i} = i \sum ∣ A_{i} ∣ - i < j \sum ∣ A_{i} \cap A_{j} ∣ + i < j < l \sum ∣ A_{i} \cap A_{j} \cap A_{l} ∣ - \dots + (- 1)^{n + 1} ∣ A_{1} \cap \dots \cap A_{n} ∣ .

Standard applications: counting numbers divisible by at least one of a set of primes, counting surjective functions, Euler’s totient (see General), and derangements (below).

// counts integers in [1, N] divisible by at least one of the given primes
long long countDivisibleByAny(long long N, vector<long long> &primes) {
    int k = primes.size();
    long long total = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        long long lcm = 1;
        int bits = __builtin_popcount(mask);
        bool overflow = false;
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                long long g = __gcd(lcm, primes[i]);
                if (lcm / g > N / primes[i]) { overflow = true; break; }
                lcm = lcm / g * primes[i];
            }
        }
        if (overflow) continue;
        long long term = N / lcm;
        total += (bits % 2 == 1) ? term : -term;
    }
    return total;
}

Time Complexity: $O (2^{k} \cdot k)$ for $k$ sets

Derangements

Permutations of $n$ elements with no fixed points.

D_{n} = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !} .

D_{n} = (n - 1) (D_{n - 1} + D_{n - 2}), D_{0} = 1, D_{1} = 0.

Mathematical Proof

Applying Inclusion-Exclusion to the events ” $i$ is a fixed point” over all $n$ positions gives $D_{n} = \sum_{i = 0}^{n} (- 1)^{i} (i n) (n - i)! = n! \sum_{i = 0}^{n} \frac{( - 1 ) ^{i}}{i !}$ .

long long derangements(int n, long long mod) {
    vector<long long> D(n + 1);
    D[0] = 1;
    if (n >= 1) D[1] = 0;
    for (int i = 2; i <= n; i++)
        D[i] = (i - 1) * ((D[i - 1] + D[i - 2]) % mod) % mod;
    return D[n];
}

Time Complexity: $O (n)$

Burnside’s Lemma

Counts the number of distinct objects up to the symmetry of a group $G$ acting on a set $X$ :

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum ∣ X^{g} ∣,

where $X^{g}$ is the set of elements of $X$ fixed by $g$ .

Classic example — necklaces: count distinct necklaces of $n$ beads and $k$ colors under rotation. A rotation by $d$ positions decomposes the $n$ beads into $g cd (n, d)$ cycles, and a coloring is fixed by that rotation iff it’s constant on every cycle — giving $k^{g c d (n, d)}$ fixed colorings.

long long distinctNecklaces(int n, int k, long long mod) {
    long long total = 0;
    for (int d = 0; d < n; d++) {
        int g = __gcd(n, d);
        total = (total + modpow(k, g, mod)) % mod;
    }
    return total * modinv(n, mod) % mod; // modinv from Modular Arithmetic
}

Time Complexity: $O (n lo g (mod))$

Pólya Enumeration Theorem

A restatement of Burnside’s Lemma specialized to coloring problems: since a coloring is fixed by $g$ exactly when it’s constant on every cycle of $g$ , $∣ X^{g} ∣ = k^{c (g)}$ where $c (g)$ is the number of cycles in $g$ ‘s permutation of the underlying positions. This gives

∣ X / G ∣ = \frac{1}{∣ G ∣} g \in G \sum k^{c (g)} .

The necklace-counting code above is already an instance of PET: rotation by $d$ decomposes $n$ positions into $c (g) = g cd (n, d)$ cycles. PET becomes essential (over plain Burnside) once the group $G$ includes more complex symmetries (e.g. reflections, or automorphisms of a graph), where $c (g)$ must be computed from the specific permutation structure of each $g$ rather than a simple $g cd$ .

Generating Functions

Ordinary Generating Function (OGF) of a sequence $a_{0}, a_{1}, a_{2}, \dots$ :

A (x) = n \geq 0 \sum a_{n} x^{n} .

Sequence operations become algebraic operations on the generating function: shifting the sequence corresponds to multiplying by $x$ , and convolution ( $c_{n} = \sum_{i} a_{i} b_{n - i}$ ) corresponds to multiplying the two generating functions, $C (x) = A (x) B (x)$ .

Examples:

Fibonacci: F (x) = \frac{x}{1 - x - x ^{2}}, Catalan: C (x) = \frac{1 - 1 - 4 x}{2 x}, Stars-and-bars (k bins): (\frac{1}{1 - x})^{k} .

Exponential Generating Function (EGF), used for labeled structures:

A (x) = n \geq 0 \sum a_{n} \frac{x ^{n}}{n !} .

Example: the EGF for permutations of $n$ labeled items is $\frac{1}{1 - x}$ ; the EGF for derangements is $\frac{e ^{- x}}{1 - x}$ .

In competitive programming, generating functions are mainly wielded through polynomial multiplication (convolution), often accelerated with NTT (see the 998244353 modulus in Modular Arithmetic), to compute an entire sequence’s terms in bulk rather than one value at a time.

Stirling Numbers

First kind $[k n]$ — number of permutations of $n$ elements with exactly $k$ cycles:

[k n] = [k - 1 n - 1] + (n - 1) [k n - 1] .

Second kind ${k n}$ — number of ways to partition a set of $n$ labeled elements into exactly $k$ non-empty subsets:

{k n} = {k - 1 n - 1} + k {k n - 1} .

vector<vector<long long>> stirlingSecondKind(int n, long long mod) {
    vector<vector<long long>> S(n + 1, vector<long long>(n + 1, 0));
    S[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            S[i][j] = (S[i - 1][j - 1] + 1LL * j * S[i - 1][j]) % mod;
    return S;
}

Time Complexity: $O (n^{2})$

Bell Numbers

Total number of ways to partition a set of $n$ labeled elements into any number of non-empty subsets:

B_{n} = k = 0 \sum n {k n} .

Computed directly with the Bell triangle, avoiding the need to build the full Stirling table:

a_{i, 0} = a_{i - 1, i - 1}, a_{i, j} = a_{i, j - 1} + a_{i - 1, j - 1}, B_{n} = a_{n, 0} .

vector<long long> bellNumbers(int n, long long mod) {
    vector<vector<long long>> tri(n + 1);
    tri[0] = {1};
    vector<long long> B(n + 1);
    B[0] = 1;
    for (int i = 1; i <= n; i++) {
        tri[i].assign(i + 1, 0);
        tri[i][0] = tri[i - 1][i - 1];
        for (int j = 1; j <= i; j++)
            tri[i][j] = (tri[i][j - 1] + tri[i - 1][j - 1]) % mod;
        B[i] = tri[i][0];
    }
    return B;
}

Time Complexity: $O (n^{2})$

Partition Numbers

The integer partition function $p (n)$ counts the number of ways to write $n$ as a sum of positive integers, ignoring order.

n \geq 0 \sum p (n) x^{n} = k = 1 \prod \infty \frac{1}{1 - x ^{k}} .

Computed with a coin-change-style DP that builds every value up to $n$ using parts $1 \dots n$ :

vector<long long> partitionNumbers(int n, long long mod) {
    vector<long long> p(n + 1, 0);
    p[0] = 1;
    for (int part = 1; part <= n; part++)
        for (int i = part; i <= n; i++)
            p[i] = (p[i] + p[i - part]) % mod;
    return p;
}

Time Complexity: $O (n^{2})$
Space Complexity: $O (n)$

Recurrence Relations

A linear homogeneous recurrence with constant coefficients has the form

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k} .

Its behavior is governed by the characteristic equation

x^{k} = c_{1} x^{k - 1} + c_{2} x^{k - 2} + \dots + c_{k},

whose roots $x_{1}, \dots, x_{k}$ give the closed form $a_{n} = \sum_{i} α_{i} x_{i}^{n}$ (for distinct roots), with the $α_{i}$ fixed by the initial conditions.

For competitive programming, the practical takeaway is that any such recurrence can be evaluated for huge $n$ in $O (k^{3} lo g n)$ by encoding one step of the recurrence as a $k \times k$ transition matrix and applying Matrix Exponentiation. For example, Fibonacci’s $a_{n} = a_{n - 1} + a_{n - 2}$ becomes

(a_{n + 1} a_{n}) = (1110) (a_{n} a_{n - 1}) .

Pigeonhole Principle

Naive form. If more than $n$ objects are placed into $n$ boxes, at least one box contains more than one object.

General form. If $p$ pigeons are placed into $k$ holes, at least one hole contains at least $⌈ p / k ⌉$ pigeons.

Generalized form. If more than $k \cdot n$ objects are placed into $n$ boxes, at least one box contains more than $k$ objects.

Application is usually a two-step process: identify what the “pigeons” and “holes” are, then finish with problem-specific reasoning once the principle guarantees a collision.

❄️Competitive Programming

Directory

Combinatorics

Permutations

Combinations

Binomial Theorem

Computing nCr Fast, Modulo a Prime

Code — Factorial / Inverse-Factorial Precomputation

Code — Pascal’s-Triangle DP (Small n, No Modular Inverse Needed)

Catalan Numbers

Stars and Bars

Inclusion-Exclusion Principle

Derangements

Burnside’s Lemma

Pólya Enumeration Theorem

Generating Functions

Stirling Numbers

Bell Numbers

Partition Numbers

Recurrence Relations

Pigeonhole Principle

Graph View

Table of Contents

Recent notes

Welcome to Algopedia

🐬 Base

General

General

Constructive Algorithms

title	Combinatorics
modified	—