DAG上不相交路径计数

Some Definitions

该DAG为\(G=(V,E)\)。
\(\omega(P)\)为\(P\)这条路径上的所有边权的积。
\(e(u,v)\)表示\(u\)到\(v\)的每一条路径\(P\)的\(\omega(P)\)之和。
起点集\(A\)和终点集\(B\)满足\(A,B\subseteq V\wedge|A|=|B|=n\)。
一组\(A\rightarrow B\)的不相交路径\(S\)：\(P_i\)是一条\(A_i\rightarrow B_{p_i}\)的路径，其中\(p\)是一个排列，且任意两个\(P_i\)没有公共顶点。
\(\tau(p)\)为\(p\)的逆序对数。

Lindstr?m–Gessel–Viennot引理

\(\mathbf M_{n*n}\)满足\(\mathbf M_{i,j}=e(A_i,B_j)\)。
则有\(\det(\mathbf M)=\sum\limits_{S:A\rightarrow B}(-1)^{\tau(p)}\prod\limits_{i=1}^n\omega(P_i)\)。
其中\(S:A\rightarrow B\)表示\(S\)是一组\(A\rightarrow B\)的不相交路径。

Talaska把这个引理扩展至了任意有向图。但是似乎找不到什么资料。

DAG上不相交路径计数

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12142462.html