LGV Lemma
Overview
The Lindström–Gessel–Viennot lemma, or LGV lemma for short, handles problems such as counting non-intersecting paths in a directed acyclic graph.
Prerequisite reading: the basics in Graph Theory Concepts, Matrices, and computing determinants by Gaussian elimination.
The LGV lemma applies only to directed acyclic graphs.
Definition
\(\omega(P)\) denotes the product of the edge weights of all edges on the path \(P\). (When counting paths, set every edge weight to \(1\).) (In fact, the edge weights may be generating functions.)
\(e(u, v)\) denotes the sum of \(\omega(P)\) over every path \(P\) from \(u\) to \(v\), that is, \(e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)\).
The set of start vertices \(A\) is a subset of the vertex set of the directed acyclic graph, of size \(n\).
The set of end vertices \(B\) is likewise a subset of the vertex set of the directed acyclic graph, also of size \(n\).
A system \(S\) of non-intersecting paths \(A\rightarrow B\) consists of paths \(S_i\) from \(A_i\) to \(B_{\sigma(S)_i}\), where \(\sigma(S)\) is a permutation, such that \(S_i\) and \(S_j\) have no common vertex for any \(i\ne j\).
\(t(\sigma)\) denotes the number of inversions of the permutation \(\sigma\).
Lemma
Here \(\sum\limits_{S:A\rightarrow B}\) runs over every system \(S\) of non-intersecting paths \(A\rightarrow B\) that meets the requirements above.
Proof
By the definition of the determinant,
Observe that \(\prod\limits_{i=1}^n \sum\limits_{P:A_i\to B_{\sigma(i)}} \omega(P)\) is in fact the sum of \(\omega(P)\) over all path systems \(P\) from \(A\) to \(B\) whose permutation is \(\sigma\).
Here \(P\) is an arbitrary path system.
Let \(U\) range over the non-intersecting path systems and \(V\) over the intersecting ones. Then
Suppose \(P\) contains a pair of intersecting paths \(P_i:a_1 \to u \to b_1,P_j:a_2 \to u \to b_2\). Then there is a corresponding pair of intersecting paths \(P_i'=a_1\to u\to b_2,P_j'=a_2\to u\to b_1\), where the other paths of \(P'\) are the same as those of \(P\). This gives \(\omega(P)=\omega(P'),t(P)=t(P')\pm 1\).
Therefore \(\sum\limits_{V:A\to B}(-1)^{t(\sigma)}\prod\limits_{i=1}^n \omega(V_i)=0\).
Hence \(\det(M)=\sum\limits_{U:A\to B}(-1)^{t(U)}\prod\limits_{i=1}^n \omega(U_i)\).
This completes the proof1.
Example problems
Example 1: CF348D Turtles
Problem statement: in an \(n\times m\) grid, some cells can be walked on and some cannot. A turtle at \((x, y)\) can only move to \((x+1, y)\) or \((x, y+1)\). Find the number of non-intersecting paths of the turtle from \((1, 1)\) to \((n, m)\), modulo \(10^9+7\). Here \(2\le n,m\le3000\).
This is a fairly direct application of the LGV lemma. Look at all valid paths: every path that leaves \((1,1)\) must pass through \(A=\{(1,2), (2,1)\}\), and every path that reaches the end vertex must pass through \(B=\{(n-1, m), (n, m-1)\}\), so \(A, B\) can be chosen at once. By the LGV lemma the answer is
where \(f(a, b)\) is the number of paths \(a\rightarrow b\) in the graph. Counting paths among blocked lattice points is a straightforward \(O(nm)\) DP, so \(f\) is easy to compute. The whole solution runs in \(O(nm)\).
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | |
Example 2: HDU 5852 Intersection is not allowed!
Problem statement: on an \(n\times n\) board, a piece at \((x, y)\) can only move to \((x, y+1)\) or \((x + 1, y)\). There are \(k\) pieces; the \(i\)-th starts at \((1, a_i)\) and has to reach \((n, b_i)\), and the paths must be pairwise non-intersecting. Find the number of ways modulo \(10^9+7\). Constraints: \(1\le n\le 10^5\), \(1\le k\le 100\), and it is guaranteed that \(1\le a_1<a_2<\dots<a_k\le n\), \(1\le b_1<b_2<\dots<b_k\le n\).
If the paths do not intersect, the path from \(a_i\) must end at \(b_i\). So \(\sigma(S)_i=i\) always holds in the LGV lemma, and signs are not an issue. Set every edge weight to \(1\) and apply the lemma directly.
The number of paths from \((1, a_i)\) to \((n, b_j)\) is the number of ways to choose which \(n-1\) of the \(n-1+b_j-a_i\) steps go down, so \(e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}\).
The determinant can be computed by Gaussian elimination.
This runs in \(O(n+k(k^2 + \log p))\), where \(\log p\) is the cost of computing a modular inverse.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | |
References
-
The proof is taken from Zhihu - Proof of the LGV Lemma (in Chinese) ↩
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: ouuan, 24OI-bot, Ir1d, memset0, Enter-tainer, kenlig, lxdlam, H-J-Granger, Tiphereth-A, Menci, Cidoai, HeRaNO, c-forrest, chenyichen0420 (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.