定义

LGV 引理全称为 Lindström–Gessel–Viennot lemma，适用于有向无环图。

令 $\omega(Q)=\prod_{(x\to y)\in Q}W(x,y)$，其中 $Q$ 为有向无环图中的一条路径，$W(x,y)$ 表示 $x\to y$ 这条边上的边权，对于没有边权的计数类问题 $W(x,y)$ 可以设置为 $x\to y$ 中重边的数量。也就是说，$\omega(Q)$ 的值为路径 $Q$ 中所有边权的积。

令 $e(x,y)=\sum_{Q:(x\to y)}\omega(Q)$，也就是所有起点为 $x$ 终点为 $y$ 的路径 $Q$ 的 $\omega(Q)$ 的和。如果边权为重边的个数，那么 $e(x,y)$ 表示的就是从 $x$ 到 $y$ 之间的所有路径数。

定义起点集合 $A=\{a_1,a_2,\cdots,a_n\}$，终点集合 $B=\{b_1,b_2,\cdots,b_n\}$。

路径 $P_i$ 表示从 $a_i$ 到 $b_{\sigma_{i}}$ 的路径，其中 $\sigma$ 为一个 $1$ 到 $n$ 的排列。

定义 $\omega(P)=\prod_{i=1}^{n}\omega(P_i)$，也就是该路径组考虑重边情况下的方案数。

定义 $\tau(\sigma)$ 表示排列 $\sigma$ 的逆序对个数，$\tau(P)=\sum\tau(P_i)$ 也就是涉及的所有的 $\tau(\sigma)$ 的和。

记矩阵$M$，其意义如下：

$M=\begin{bmatrix} e(a_1,b_1) & e(a_1,b_2) & \cdots & e(a_1,b_n)\\ e(a_2,b_1) & e(a_2,b_2) & \cdots & e(a_2,b_n)\\ \vdots & \vdots & \ddots & \vdots\\ e(a_n,b_1) & e(a_n,b_2) & \cdots & e(a_n,b_n) \end{bmatrix}$

则 $\det(M)=\sum_{P}(-1)^{\tau(P)}\omega(P_i)$，其中 $𝑃$ 为不含公共点的路径组。

根据 LGV 引理的内容，此时的 $\operatorname{det}(M)$ 的值为路径组 $P$ 中所有的不相交的路径的方案数。

当边权为重边个数时，$\operatorname{det}(M)$ 意义为逆序对为偶数的不相交路径组数减逆序对为奇数的不相交路径组数。

证明

将上方的式子展开：

$\det(M)=\sum_{P}(-1)^{\tau(P)}\omega(P_i)$

得到一个新式子：

$\operatorname{det}(M)=\sum_{\sigma}(-1)^{\tau(P)}\prod_{i=1}^{n}\sum_{P:a_i\to b_i}\omega(P)$

通过观察容易得到：

$\prod_{i=1}^{n}\sum_{P:a_i\to b_i}\omega(P)=\sum_{P:A\to B}\omega(P)$

那么将其带回原式得到：

$\operatorname{det}(M)=\sum_{P:A\to B}(-1)^{\tau(P)}\omega(P)$

观察易得此时的 $\operatorname{det}(M)$ 表示的所有路径组方案数的带符号和。

将 $P$ 划分为两个部分 $U$ 和 $V$ 分别表示不相交的路径和相交的路径，那么可以将原式再次变形：

$\operatorname{det}(M)=\sum_{U:A\to B}(-1)^{\tau(U)}\omega(U)+\sum_{V:A\to B}(-1)^{\tau(V)}\omega(V)$

所以实际上定理说明的是 $\sum_{V:A\to B}(-1)^{\tau(V)}\omega(V)=0$ 因为 $\operatorname{det}(M)$ 的值就是 $\sum_{U:A\to B}(-1)^{\tau(U)}\omega(U)$。

在相交路径组中，找到最小的一对 $(i,j)$ 满足 $P_i,P_j$ 之间存在交点。假设他们最先相交于 $u$，那么交换 $\sigma_{i}$ 和 $\sigma_j$ 可以发现他们只相差一个符号，因此和为 $0$。

因此 LGV 引理得证。