Lindström–Gessel–Viennot lemma

Let a finite directed acyclic graph have weighted edges, sources $a_1,\dots ,a_r$ and sinks $b_1,\dots ,b_r$. Let $M_{ij}$ be the sum of products of edge weights over directed paths from $a_i$ to $b_j$. The Lindström-Gessel-Viennot lemma says that $\det M$ is the signed weighted sum of vertex-disjoint path families, with sign given by the permutation pairing sources to sinks. Expand the determinant: families with an intersection cancel by exchanging the tails of two paths at the first shared vertex, a sign-reversing involution. In planar arrangements where only the identity pairing can be disjoint, the determinant directly counts disjoint lattice paths.