Lindström–Gessel–Viennot Lemma — Non-Intersecting Lattice Paths

January 2026 · 28 min read

The Counting Problem

Imagine an m × n grid. You have k tokens, each starting at a distinct source cell and needing to reach a distinct sink cell. Every token moves only right or up. The constraint: no two paths may share a vertex. How many such tuples of non-intersecting paths exist?

This problem arises naturally in tiling enumeration, Young tableaux counting, and dozens of competitive-programming challenges. A naive inclusion–exclusion over all pairs of path intersections is doubly exponential in k. Even for k = 2, manually subtracting intersecting pairs from the product of individual path counts is tedious and error-prone.

The Lindström–Gessel–Viennot (LGV) lemma replaces all of this with a single determinant. It is one of the most elegant tools in enumerative combinatorics, and once you know it, many problems that look terrifying become routine.

Why Naive Approaches Fail

Suppose we have k source-sink pairs. The number of individual paths from source a_i to sink b_j is easy to compute (often a single binomial coefficient). But counting tuples where no two paths cross requires careful bookkeeping of geometric intersections. The inclusion–exclusion formula alternates over all subsets of pairs, leading to 2^O(k²) terms. The LGV lemma reduces this to computing a single k × k determinant — O(k³) work.

The LGV Lemma

Setup

Let G be a locally finite directed acyclic graph (DAG). Fix two sequences of vertices:

• Sources: A = (a₁, a₂, …, a_n)
• Sinks: B = (b₁, b₂, …, b_n)

For any two vertices u, v define e(u, v) as the number of directed paths from u to v (or more generally, the sum of weights of all such paths). Construct the path matrix:

M[i][j] = e(a_i, b_j)

The "identity only" condition is the common case in competitive programming: sources are ordered left-to-right and sinks are ordered left-to-right on a grid, so any non-identity permutation would force paths to cross.

Proof Outline — Sign-Reversing Involution

Expand det(M) by definition. Each term σ corresponds to a tuple of paths (a_i → b_σ(i)). If those paths don't intersect, the tuple is counted with sign sgn(σ). If they do intersect, we construct a sign-reversing involution:

1. Find the first (lexicographically) intersection point p shared by paths P_i and P_j (i < j).
2. Swap the tails of P_i and P_j after p. This maps the tuple to another tuple whose permutation differs by a transposition, flipping the sign.
3. The map is its own inverse (an involution), so intersecting tuples cancel in pairs.

What survives after all cancellation are exactly the non-intersecting path tuples, each counted with sign sgn(σ). When only σ = id can produce non-intersecting tuples, every surviving term has sign +1, and det(M) is the unsigned count.

Weighted Version

If each edge has a weight and the weight of a path is the product of its edge weights, then e(u, v) is the sum of weights over all paths from u to v, and det(M) gives the signed sum of weights of non-intersecting path systems. This is essential for generating-function applications.

Lattice Path Counting

Basic Grid Paths

On a grid, a path from (x₁, y₁) to (x₂, y₂) using only right (R) and up (U) steps exists only when x₂ ≥ x₁ and y₂ ≥ y₁. The number of such paths is:

e((x₁,y₁), (x₂,y₂)) = C(dx + dy, dx)

where dx = x₂ − x₁ and dy = y₂ − y₁. Each path is a sequence of dx + dy steps, of which we choose dx to be right-steps (the rest are up-steps). This is the fundamental building block for the LGV path matrix.

Catalan Numbers via Reflection

The number of lattice paths from (0, 0) to (n, n) that never cross above the diagonal y = x equals the n-th Catalan number:

C_n = C(2n, n) / (n + 1) = C(2n, n) − C(2n, n − 1)

The classical proof uses André's reflection principle: a bad path (one that touches y = x + 1) is reflected across that line, creating a bijection with paths from (−1, 1) to (n, n). We will see shortly that Catalan numbers also arise naturally from a 2 × 2 LGV determinant, providing an elegant alternative proof.

Paths with Obstacles

When certain grid cells are blocked, direct binomial formulas no longer apply. We use DP on the grid, or combine LGV with inclusion–exclusion over obstacle positions. For a single forbidden point f, the count of paths from a to b avoiding f is e(a, b) − e(a, f) · e(f, b). Multiple forbidden points require more care, but the LGV framework handles the non-intersection constraint orthogonally.

Worked Examples

Example A: Two Non-Intersecting Paths (2 × 2 Determinant)

Problem: On a grid, find the number of pairs of non-intersecting paths where path 1 goes from (0, 0) to (4, 3) and path 2 goes from (1, 0) to (5, 3).

Build the 2 × 2 path matrix M:

• M[1][1] = e((0,0), (4,3)) = C(7, 4) = 35
• M[1][2] = e((0,0), (5,3)) = C(8, 5) = 56
• M[2][1] = e((1,0), (4,3)) = C(6, 3) = 20
• M[2][2] = e((1,0), (5,3)) = C(7, 4) = 35

Apply LGV:

det(M) = 35 · 35 − 56 · 20 = 1225 − 1120 = 105

So there are 105 pairs of non-intersecting lattice paths. Without LGV, we would need to enumerate which cells the paths share and apply inclusion–exclusion — a much more complex computation.

Example B: Catalan Numbers via LGV

Claim: The n-th Catalan number C_n counts the number of non-intersecting path pairs from A = ((0, 0), (1, 0)) to B = ((n − 1, n), (n, n − 1)) on the integer lattice (but it is cleaner to use shifted sinks).

A more standard formulation: count non-intersecting pairs from (0, 0) and (0, 1) to (n, n) and (n, n + 1). The path matrix is:

• M[1][1] = e((0,0), (n,n)) = C(2n, n)
• M[1][2] = e((0,0), (n, n+1)) = C(2n+1, n)
• M[2][1] = e((0,1), (n,n)) = C(2n−1, n)
• M[2][2] = e((0,1), (n, n+1)) = C(2n, n)

Computing the determinant:

det(M) = C(2n, n)² − C(2n+1, n) · C(2n−1, n)

Using the identity C(2n+1, n) = 2 · C(2n, n) · (2n+1) / (2(n+1)) and simplifying, this reduces to C(2n, n) / (n + 1), the n-th Catalan number. This gives an algebraic proof of the ballot/Dyck-path interpretation of Catalan numbers entirely through the LGV framework.

Example C: Counting Rhombus Tilings

A classic application: the number of rhombus tilings of a regular hexagon with side lengths (a, b, c) equals the number of non-intersecting path tuples on a triangular lattice. Using LGV, this count equals the determinant of an a × a matrix whose entries are binomial coefficients:

∏_i,j,k (i + j + k − 1) / (i + j + k − 2)   (MacMahon's box formula)

For a = b = c = n, this specialises to the formula for the number of plane partitions inside an n × n × n box. The LGV determinant approach is one of the standard proofs of MacMahon's result.

C++ Implementation

Modular Arithmetic Utilities

Since path counts involve large binomial coefficients, we work modulo a prime p (typically 10⁹ + 7). We need fast modular exponentiation, modular inverse, and precomputed factorials.

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

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

long long fac[MAXN], inv_fac[MAXN];

long long power(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() {
    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;
}

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

Building the Path Matrix

Given sources (a_i.x, a_i.y) and sinks (b_j.x, b_j.y), entry M[i][j] is the number of right/up lattice paths between them:

struct Point { int x, y; };

// Build the n x n path matrix for LGV
vector<vector<long long>> buildMatrix(
    vector<Point>& src, vector<Point>& dst) {
    int n = src.size();
    vector<vector<long long>> M(n, vector<long long>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            int dx = dst[j].x - src[i].x;
            int dy = dst[j].y - src[i].y;
            M[i][j] = C(dx + dy, dx);  // 0 if dx<0 or dy<0
        }
    return M;
}

Determinant Modulo a Prime

We compute the determinant using Gaussian elimination mod p. Since p is prime, every non-zero element has a modular inverse.

long long determinant(vector<vector<long long>> M) {
    int n = M.size();
    long long det = 1;
    for (int col = 0; col < n; col++) {
        // Find pivot
        int pivot = -1;
        for (int row = col; row < n; row++) {
            if (M[row][col] != 0) { pivot = row; break; }
        }
        if (pivot == -1) return 0;  // singular

        if (pivot != col) {
            swap(M[pivot], M[col]);
            det = (MOD - det) % MOD;  // swap flips sign
        }

        det = det % MOD * M[col][col] % MOD;
        long long inv = power(M[col][col], MOD - 2, MOD);

        for (int row = col + 1; row < n; row++) {
            long long factor = M[row][col] % MOD * inv % MOD;
            for (int k = col; k < n; k++) {
                M[row][k] = (M[row][k] - factor * M[col][k] % MOD + MOD) % MOD;
            }
        }
    }
    return (det % MOD + MOD) % MOD;
}

Putting It All Together

A complete solution that reads n source-sink pairs and outputs the number of non-intersecting lattice path systems modulo 10⁹ + 7:

int main() {
    precompute();

    int n;
    cin >> n;

    vector<Point> src(n), dst(n);
    for (int i = 0; i < n; i++)
        cin >> src[i].x >> src[i].y;
    for (int i = 0; i < n; i++)
        cin >> dst[i].x >> dst[i].y;

    auto M = buildMatrix(src, dst);
    cout << determinant(M) << "\n";
    return 0;
}

DP-Based Path Counting on General DAGs

When the graph is not a simple grid (e.g., a DAG with forbidden cells or weighted edges), replace the binomial coefficient with a DP over the DAG:

// Count paths in a grid with forbidden cells
// forbidden[x][y] = true if cell (x,y) is blocked
long long pathCountDP(Point s, Point t,
                      vector<vector<bool>>& forbidden) {
    int dx = t.x - s.x, dy = t.y - s.y;
    if (dx < 0 || dy < 0) return 0;

    // dp[i][j] = paths from s to (s.x+i, s.y+j)
    vector<vector<long long>> dp(dx + 1, vector<long long>(dy + 1, 0));
    dp[0][0] = forbidden[s.x][s.y] ? 0 : 1;

    for (int i = 0; i <= dx; i++)
        for (int j = 0; j <= dy; j++) {
            if (i == 0 && j == 0) continue;
            if (forbidden[s.x + i][s.y + j]) { dp[i][j] = 0; continue; }
            long long val = 0;
            if (i > 0) val += dp[i - 1][j];
            if (j > 0) val += dp[i][j - 1];
            dp[i][j] = val % MOD;
        }
    return dp[dx][dy];
}

Use this DP to fill each entry M[i][j] of the path matrix, then compute det(M) as before. Total complexity: O(n² · grid_size + n³).

Connection to Determinants

Why Determinants Count Paths

The determinant of a matrix M is defined as Σ_σ sgn(σ) ∏ M[i][σ(i)]. Each term is a product of path counts — one path per source-sink pair — weighted by the sign of the permutation. The sign-reversing involution on intersecting paths exactly mirrors the algebraic cancellation in the determinant. This is why the determinant is the "right" object: its built-in sign bookkeeping handles inclusion–exclusion automatically.

Relation to the Karlin–McGregor Theorem

The continuous analogue of LGV is the Karlin–McGregor theorem (1959), which states that the probability of non-intersecting continuous-time Markov chains equals a determinant of transition probabilities. LGV is essentially the discrete, combinatorial version. In problems involving random walks on lattices, both tools apply depending on whether the setting is discrete or continuous.

Schur Polynomials and Generating Functions

The generating function for non-intersecting lattice paths from sources (0, λ₁), (1, λ₂), … to sinks (n−1, μ₁), (n, μ₂), … is a Schur polynomial s_λ/μ(x₁, …, x_n). This is the Jacobi–Trudi identity:

s_λ = det(h_{λi − i + j})

where h_k is the k-th complete homogeneous symmetric polynomial. The LGV lemma provides a combinatorial proof of this fundamental identity in symmetric-function theory. For CP, this connection is mostly useful as background knowledge — but it explains why determinants of binomial coefficients keep appearing in counting problems.

Binomial Determinant Identities

Many classical determinant identities follow directly from LGV. For instance, the Vandermonde-like identity:

det(C(a_i, j))_{0 ≤ i,j ≤ n−1} = ∏_{i < j} (a_i − a_j) / ∏_i i!

Each entry C(a_i, j) counts paths in a suitable lattice, and the determinant counts non-intersecting systems. Evaluating via the lattice-path interpretation gives the product formula on the right.

CP Applications

Grid Paths with Forbidden Intersections

Typical problem: Given n source cells on the bottom edge and n sink cells on the top edge of an H × W grid, count non-intersecting right/up path tuples. This is a direct application: build the n × n binomial matrix and compute its determinant.

Counting Standard Young Tableaux

A Standard Young Tableau (SYT) of shape λ is a filling of the Young diagram with 1, 2, …, n such that rows and columns are increasing. Via the Robinson–Schensted correspondence, SYTs biject with non-intersecting lattice paths. The hook-length formula f^λ = n! / ∏ h(u) can be derived from an LGV determinant.

For CP, this means problems asking "count the number of SYTs of a given shape" can be solved by building the LGV matrix and computing a determinant, bypassing the hook-length formula entirely if the shape is awkward.

Binomial Determinants in Competition Problems

A recurring pattern: a problem asks you to evaluate a determinant whose entries are binomial coefficients (or products of factorials). Recognise these as LGV path matrices and exploit lattice-path interpretations to simplify or compute them.

Problem Walkthrough: CF 348D (Turtles)

Statement (simplified): Given an n × m grid with some blocked cells, count the number of pairs of non-intersecting paths where path 1 goes from (1,1) to (n,m) and path 2 goes from (1,2) to (n−1,m)… (or similar source/sink placement on adjacent corners).

Solution sketch:

1. Identify two source-sink pairs; place them so only σ = id gives non-intersecting paths.
2. Compute e(a_i, b_j) for each of the 4 entries using DP on the grid (handling blocked cells).
3. Compute the 2 × 2 determinant: M[0][0] · M[1][1] − M[0][1] · M[1][0].
4. Output det(M) mod 10⁹ + 7.

// CF 348D — Turtles (LGV, 2 non-intersecting paths)
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
int n, m;
string grid[3005];
long long dp[3005][3005];

long long pathCount(int sx, int sy, int tx, int ty) {
    // DP counting right/down paths avoiding '#'
    for (int i = sx; i <= tx; i++)
        for (int j = sy; j <= ty; j++)
            dp[i][j] = 0;

    if (grid[sx][sy] == '#') return 0;
    dp[sx][sy] = 1;
    for (int i = sx; i <= tx; i++)
        for (int j = sy; j <= ty; j++) {
            if (i == sx && j == sy) continue;
            if (grid[i][j] == '#') continue;
            if (i > sx) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            if (j > sy) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
        }
    return dp[tx][ty];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> grid[i];

    // Sources: a1=(0,1), a2=(1,0)  Sinks: b1=(n-2,m-1), b2=(n-1,m-2)
    long long M00 = pathCount(0, 1, n-2, m-1);
    long long M01 = pathCount(0, 1, n-1, m-2);
    long long M10 = pathCount(1, 0, n-2, m-1);
    long long M11 = pathCount(1, 0, n-1, m-2);

    long long ans = (M00 % MOD * M11 % MOD - M01 % MOD * M10 % MOD + MOD * 2LL) % MOD;
    cout << ans << "\n";
    return 0;
}

ICPC-Style: Counting Plane Partitions

Many ICPC regional problems reduce to counting boxed plane partitions or lozenge tilings. The standard approach:

1. Model the tiling as non-intersecting lattice paths on a triangular or rectangular grid.
2. Identify sources and sinks from the boundary conditions.
3. Build the LGV matrix (entries are binomial coefficients or DP values).
4. Compute the determinant.

The determinant often simplifies to a beautiful closed-form product (MacMahon's formula), but in CP you typically just compute it numerically mod a prime.

Summary

Complexity Summary

Common Pitfalls

• Vertex-disjoint vs edge-disjoint: LGV counts vertex-disjoint paths. If you need edge-disjoint paths, you must split vertices.
• Source/sink ordering: If sources or sinks are not in the right order, the identity permutation may not be the only one contributing non-intersecting paths. Ensure a₁ < a₂ < … and b₁ < b₂ < … in a compatible sense.
• Modular determinant signs: When computing det mod p, the intermediate value (MOD − det) correctly handles sign flips from row swaps.
• Zero entries: If some e(a_i, b_j) = 0 (no path exists), the matrix may be singular. A determinant of 0 simply means no non-intersecting system exists.

Where to Practice

1. CF 348D — Turtles — classic 2-path LGV on a grid with obstacles
2. CF 722E — Research Rover — path counting with blocked cells
3. CodeChef — Parallel Paths — non-intersecting lattice paths
4. Library Checker — determinant problems — good for testing your det code