In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973. The lemma is named after Bernt Lindström, Ira Gessel and Gérard Viennot.
Statement Let G be a locally finite directed acyclic graph. This means that each vertex has finite degree, and that G contains no directed cycles. Consider base vertices A = { a 1 , … , a n } {\displaystyle A=\{a_{1},\ldots ,a_{n}\}} and destination vertices B = { b 1 , … , b n } {\displaystyle B=\{b_{1},\ldots ,b_{n}\}} , and also assign a weight ω e {\displaystyle \omega _{e}} to each directed edge e. These edge weights are assumed to belong to some commutative ring. For each directed path P between two vertices, let ω ( P ) {\displaystyle \omega (P)} be the product of the weights of the edges of the path. For any two vertices a and b, write e(a,b) for the sum e ( a , b ) = ∑ P : a → b ω ( P ) {\displaystyle e(a,b)=\sum _{P:a\to b}\omega (P)} over all paths from a to b. If one assigns the weight 1 to each edge, then e(a,b) is the number of paths from a to b. With this setup, write
M = ( e ( a 1 , b 1 ) e ( a 1 , b 2 ) ⋯ e ( a 1 , b n ) e ( a 2 , b 1 ) e ( a 2 , b 2 ) ⋯ e ( a 2 , b n ) ⋮ ⋮ ⋱ ⋮ e ( a n , b 1 ) e ( a n , b 2 ) ⋯ e ( a n , b n ) ) {\displaystyle M={\begin{pmatrix}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{pmatrix}}} . An n-tuple of non-intersecting paths from A to B means an n-tuple (P1, ..., Pn) of paths in G with the following properties:
There exists a permutation σ {\displaystyle \sigma } of { 1 , 2 , . . . , n } {\displaystyle \left\{1,2,...,n\right\}} such that, for every i, the path Pi is a path from a i {\displaystyle a_{i}} to b σ ( i ) {\displaystyle b_{\sigma (i)}} . Whenever i ≠ j {\displaystyle i\neq j} , the paths Pi and Pj have no two vertices in common (not even endpoints). Given such an n-tuple (P1, ..., Pn), we denote by σ ( P ) {\displaystyle \sigma (P)} the permutation of σ {\displaystyle \sigma } from the first condition. The Lindström–Gessel–Viennot lemma then states that the determinant of M is the signed sum over all n-tuples P = (P1, ..., Pn) of non-intersecting paths from A to B:
det ( M ) = ∑ ( P 1 , … , P n ) : A → B s i g n ( σ ( P ) ) ∏ i = 1 n ω ( P i ) . {\displaystyle \det(M)=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\prod _{i=1}^{n}\omega (P_{i}).}
That is, the determinant of M counts the weights of all n-tuples of non-intersecting paths starting at A and ending at B, each affected with the sign of the corresponding permutation of ( 1 , 2 , … , n ) {\displaystyle (1,2,\ldots ,n)} , given by P i {\displaystyle P_{i}} taking a i {\displaystyle a_{i}} to b σ ( i ) {\displaystyle b_{\sigma (i)}} . In particular, if the only permutation possible is the identity (i.e., every n-tuple of non-intersecting paths from A to B takes ai to bi for each i) and we take the weights to be 1, then det(M) is exactly the number of non-intersecting n-tuples of paths starting at A and ending at B.
Proof To prove the Lindström–Gessel–Viennot lemma, we first introduce some notation. An n-path from an n-tuple ( a 1 , a 2 , … , a n ) {\displaystyle (a_{1},a_{2},\ldots ,a_{n})} of vertices of G to an n-tuple ( b 1 , b 2 , … , b n ) {\displaystyle (b_{1},b_{2},\ldots ,b_{n})} of vertices of G will mean an n-tuple ( P 1 , P 2 , … , P n ) {\displaystyle (P_{1},P_{2},\ldots ,P_{n})} of paths in G, with each P i {\displaystyle P_{i}} leading from a i {\displaystyle a_{i}} to b i {\displaystyle b_{i}} . This n-path will be called non-intersecting just in case the paths Pi and Pj have no two vertices in common (including endpoints) whenever i ≠ j {\displaystyle i\neq j} . Otherwise, it will be called entangled. Given an n-path P = ( P 1 , P 2 , … , P n ) {\displaystyle P=(P_{1},P_{2},\ldots ,P_{n})} , the weight ω ( P ) {\displaystyle \omega (P)} of this n-path is defined as the product ω ( P 1 ) ω ( P 2 ) ⋯ ω ( P n ) {\displaystyle \omega (P_{1})\omega (P_{2})\cdots \omega (P_{n})} . A twisted n-path from an n-tuple ( a 1 , a 2 , … , a n ) {\displaystyle (a_{1},a_{2},\ldots ,a_{n})} of vertices of G to an n-tuple ( b 1 , b 2 , … , b n ) {\displaystyle (b_{1},b_{2},\ldots ,b_{n})} of vertices of G will mean an n-path from ( a 1 , a 2 , … , a n ) {\displaystyle (a_{1},a_{2},\ldots ,a_{n})} to ( b σ ( 1 ) , b σ ( 2 ) , … , b σ ( n ) ) {\displaystyle \left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)} for some permutation σ {\displaystyle \sigma } in the symmetric group S n {\displaystyle S_{n}} . This permutation σ {\displaystyle \sigma } will be called the twist of this twisted n-path, and denoted by σ ( P ) {\displaystyle \sigma (P)} (where P is the n-path). This, of course, generalises the notation σ ( P ) {\displaystyle \sigma (P)} introduced before. Recalling the definition of M, we can expand det M as a signed sum of permutations; thus we obtain
det M = ∑ σ ∈ S n s i g n ( σ ) ∏ i = 1 n e ( a i , b σ ( i ) ) = ∑ σ ∈ S n s i g n ( σ ) ∏ i = 1 n ∑ P i : a i → b σ ( i ) ω ( P i ) = ∑ σ ∈ S n s i g n ( σ ) ∑ { ω ( P ) : P an n -path from ( a 1 , a 2 , … , a n ) to ( b σ ( 1 ) , b σ ( 2 ) , … , b σ ( n ) ) } = ∑ { s i g n ( σ ( P ) ) ω ( P ) : P a twisted n -path from ( a 1 , a 2 , … , a n ) to ( b 1 , b 2 , . . . , b n ) } = ∑ { s i g n ( σ ( P ) ) ω ( P ) : P a non-intersecting twisted n -path from ( a 1 , a 2 , … , a n ) to ( b 1 , b 2 , . . . , b n ) } + ∑ { s i g n ( σ ( P ) ) ω ( P ) : P an entangled twisted n -path from ( a 1 , a 2 , … , a n ) to ( b 1 , b 2 , . . . , b n ) } = ∑ ( P 1 , … , P n ) : A → B s i g n ( σ ( P ) ) ω ( P ) + ∑ { s i g n ( σ ( P ) ) ω ( P ) : P an entangled twisted n -path from ( a 1 , a 2 , … , a n ) to ( b 1 , b 2 , . . . , b n ) } ⏟ = 0 ? {\displaystyle {\begin{array}{rcl}\det M&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}e(a_{i},b_{\sigma (i)})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\prod _{i=1}^{n}\sum _{P_{i}:a_{i}\to b_{\sigma (i)}}\omega (P_{i})\\&=&\sum _{\sigma \in S_{n}}\mathrm {sign} (\sigma )\sum \{\omega (P):P~{\text{an}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{a twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{a non-intersecting twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&&+\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=&\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\mathrm {sign} (\sigma (P))\omega (P)\\&&+\underbrace {\sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}} _{=0?}\\\end{array}}}
It remains to show that the sum of s i g n ( σ ( P ) ) ω ( P ) {\displaystyle \mathrm {sign} (\sigma (P))\omega (P)} over all entangled twisted n-paths vanishes. Let E {\displaystyle {\mathcal {E}}} denote the set of entangled twisted n-paths. To establish this, we shall construct an involution f : E ⟶ E {\displaystyle f:{\mathcal {E}}\longrightarrow {\mathcal {E}}} with the properties ω ( f ( P ) ) = ω ( P ) {\displaystyle \omega (f(P))=\omega (P)} and s i g n ( σ ( f ( P ) ) ) = − s i g n ( σ ( P ) ) {\displaystyle \mathrm {sign} (\sigma (f(P)))=-\mathrm {sign} (\sigma (P))} for all P ∈ E {\displaystyle P\in {\mathcal {E}}} . Given such an involution, the rest-term
∑ { s i g n ( σ ( P ) ) ω ( P ) : P an entangled twisted n -path from ( a 1 , a 2 , … , a n ) to ( b 1 , b 2 , . . . , b n ) } = ∑ P ∈ E s i g n ( σ ( P ) ) ω ( P ) {\displaystyle \sum \{\mathrm {sign} (\sigma (P))\omega (P):P~{\text{an entangled twisted}}~n{\text{-path from}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{to}}~\left(b_{1},b_{2},...,b_{n}\right)\}=\sum _{P\in {\mathcal {E}}}\mathrm {sign} (\sigma (P))\omega (P)}
in the above sum reduces to 0, since its addends cancel each other out (namely, the addend corresponding to each P ∈ E {\displaystyle P\in {\mathcal {E}}} cancels the addend corresponding to f ( P ) {\displaystyle f(P)} ). Construction of the involution: The idea behind the definition of the involution f {\displaystyle f} is to take choose two intersecting paths within an entangled path, and switch their tails after their point of intersection. There are in general several pairs of intersecting paths, which can also intersect several times; hence, a careful choice needs to be made. Let P = ( P 1 , P 2 , . . . , P n ) {\displaystyle P=\left(P_{1},P_{2},...,P_{n}\right)} be any entangled twisted n-path. Then f ( P ) {\displaystyle f(P)} is defined as follows. We call a vertex crowded if it belongs to at least two of the paths P 1 , P 2 , . . . , P n {\displaystyle P_{1},P_{2},...,P_{n}} . The fact that the graph is acyclic implies that this is equivalent to "appearing at least twice among all the paths". Since P is entangled, there is at least one crowded vertex. We pick the smallest i ∈ { 1 , 2 , … , n } {\displaystyle i\in \{1,2,\ldots ,n\}} such that P i {\displaystyle P_{i}} contains a crowded vertex. Then, we pick the first crowded vertex v on P i {\displaystyle P_{i}} ("first" in sense of "encountered first when travelling along P i {\displaystyle P_{i}} "), and we pick the largest j such that v belongs to P j {\displaystyle P_{j}} . The crowdedness of v implies j > i. Write the two paths P i {\displaystyle P_{i}} and P j {\displaystyle P_{j}} as
P i ≡ a i = u 0 → u 1 → u 2 … u α − 1 → u α