(摘自知乎）

Lindstr?m–Gessel–Viennot lemma（Lindstr?m-Gessel-Viennot lemma這里有詳細介紹跟證明）

在一個有向無環圖里，想要計算從n個起點 到n個終點 的n條互不相交的路徑的數量（具體說是其生成函數），只要符合一定條件，就有個非常漂亮的形式表達出來。具體來說是下面一個矩陣M的行列式

其中 是從第i個起點到第j個終點的生成函數。

這里最神奇的一點是為什么結果是一個行列式。這個矩陣從線性空間的角度看完全沒有意義，而實際證明過程中也完全是以組合形式證明的，結果剛好用行列式能表達出來。

證明過程用到另一個技巧，就是想證一個集合的生成函數為零是時構造一個involution，這個involution能使整個結果變號，然后整個集合就分成兩部分互相抵消。不過這個方法太寬泛，在不同問題里的變招太多，很難說是一個“技巧”。

作者：caleb89
鏈接：https://www.zhihu.com/question/59374288/answer/171857396
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

轉載于:https://www.cnblogs.com/qq1028152659/p/9347726.html

總結

以上是生活随笔為你收集整理的Lindström–Gessel–Viennot lemma的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。