简述LGV引理

LGV引理可以用于在DAG上求解不相交路径方案数问题，下面我们简单介绍一下。

一、简介

LGV引理英文全称是Lindström–Gessel–Viennot lemma，可以用来处理有向无环图上不相交路径计数等问题。在此之前，大家要先了解图论相关概念、矩阵、高斯消元求行列式等知识，能帮助大家更快理解和学习LGV引理。

LGV 引理仅适用于有向无环图。

二、定义

ω(P) 表示P这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 1）（事实上，边权可以为生成函数）

e(u,v)表示u到v的每一条路径P上的ω(P)值之和，即

起点集合A，是有向无环图点集的一个子集，大小为 n。

终点集合B，也是有向无环图点集的一个子集，大小也为 n。

一组A→B的不相交路径S：是一条从到的路径（σ(S)是一个排列），对于任何，和没有公共顶点。

N(σ)表示排列 σ 的逆序对个数。

三、引理

 其中表示满足上文要求的A→B的每一组不相交路径 S。