Lindström–Gessel–Viennotの補題
概要
Lindström–Gessel–Viennotの補題（Lindström–Gessel–Viennot lemma）とは、辺に重みをもつ有向非巡回グラフで、始点 $a_i$ から終点 $b_j$ への道の重みの和を成分とする行列の行列式が、互いに頂点を共有しない道の組の重みに置換の符号を掛けた和に等しいという定理である。証明は、交わる道の組の尾を最初の交点で入れ替える符号反転の対合による。始点と終点が両立する、たとえば平面の格子路で同じ高さに右から順に並ぶなら、行列式は交わらない道の組をそのまま数える。Jacobi–Trudi の行列式が半標準盤の和に等しいことや Cauchy–Binet の公式が従い、平面分割などの数え上げに広く使われる。
行列式 $\det(m_{ij})=\sum_{\sigma}\operatorname{sgn}(\sigma)\prod_im_{i\sigma(i)}$ は符号付きの和なので、成分が数え上げの数であっても、そのままでは何かを数えているとは言えない。Lindström–Gessel–Viennot の補題は、成分が「点 $a_i$ から点 $b_j$ への道の重みの和」である行列の行列式が、互いに交わらない道の組の重みの符号付きの和に等しいことを述べる。始点と終点の並びが平面の中でうまく揃っていれば符号はすべて $+$ になり、行列式は交わらない道の組をちょうど数える。
この記事では、補題を一般の有向非巡回グラフで述べて証明し（thm-lgv-main）、平面の格子路で始点と終点の並びが揃うための判定法を示す（prop-lgv-planar）。応用として、Schur 多項式の半標準盤による和が Jacobi–Trudi の行列式に等しいこと（thm-lgv-jacobi-trudi）と、Cauchy–Binet の公式（prop-lgv-cauchy-binet）を導く。
定義
この記事を通じて $R$ を可換環、$D=(V,E)$ を有向グラフとし、各辺 $e\in E$ に重み $w(e)\in R$ が与えられているとする。$u,v\in V$ に対し、$u$ から $v$ への道とは、頂点の列 $u=v_0,v_1,\dots,v_m=v$ であって各 $(v_{r-1},v_r)$ が辺であるものをいう（$m=0$ の 1 点だけの列も $u$ から $u$ への道とする）。道 $P$ の重み $w(P)$ はその辺の重みの積（$m=0$ なら $1$）である。
$D$ は有向非巡回グラフ（有向閉路をもたない）であり、任意の 2 頂点の間の道は有限個しかないとする。$u,v\in V$ に対し
$$
e(u,v):=\sum_{P\colon u\to v}w(P)\in R
$$
とおく（和は $u$ から $v$ への道すべてにわたる。道がなければ $0$）。正の整数 $k$ と、頂点の組 $\mathbf a=(a_1,\dots,a_k)$（始点）、$\mathbf b=(b_1,\dots,b_k)$（終点）を固定する。置換 $\sigma\in S_k$ と道 $P_i\colon a_i\to b_{\sigma(i)}$（$1\le i\le k$）の組 $(\sigma;P_1,\dots,P_k)$ を道の組といい、その重みを $w(P_1)\cdots w(P_k)$、符号を $\operatorname{sgn}(\sigma)$（置換の符号）とする。どの 2 つの道 $P_i,P_j$（$i\ne j$）も共通の頂点をもたないとき、道の組は交わらないという。
有向非巡回グラフの道は同じ頂点を 2 度通らない。2 度通るなら、その間の部分が有向閉路になるからである。
始点 $\mathbf a$ と終点 $\mathbf b$ が両立するとは、恒等置換でない $\sigma\in S_k$ に対しては、交わらない道の組 $(\sigma;P_1,\dots,P_k)$ が存在しないことをいう。
主定理
def-lgv-path-system の状況で、
$$
\det\bigl(e(a_i,b_j)\bigr)_{1\le i,j\le k}=\sum_{(\sigma;P_1,\dots,P_k)}\operatorname{sgn}(\sigma)\,w(P_1)\cdots w(P_k)
$$
が成り立つ。右辺の和は交わらない道の組すべてにわたる。特に $\mathbf a$ と $\mathbf b$ が両立するなら、
$$
\det\bigl(e(a_i,b_j)\bigr)_{1\le i,j\le k}=\sum_{(P_1,\dots,P_k)}w(P_1)\cdots w(P_k)
$$
であり、右辺は $P_i\colon a_i\to b_i$ がどの 2 つも交わらない組すべてにわたる。
行列式を展開し、各成分 $e(a_i,b_{\sigma(i)})$ を道の和に展開すると
$$
\det\bigl(e(a_i,b_j)\bigr)=\sum_{\sigma\in S_k}\operatorname{sgn}(\sigma)\prod_{i=1}^ke(a_i,b_{\sigma(i)})=\sum_{(\sigma;P_1,\dots,P_k)}\operatorname{sgn}(\sigma)\,w(P_1)\cdots w(P_k)
$$
となる。右辺はすべての道の組にわたる有限和である。そこで、交わる道の組の全体 $X$ の上に、重みを保ち符号を反転する対合 $\Phi\colon X\to X$ を作ればよい。そうすれば $X$ は $\{x,\Phi(x)\}$ の形の 2 元集合に分かれ（$\Phi(x)$ は $x$ と符号が違うので $\Phi(x)\ne x$）、各組の寄与が打ち消しあって、交わらない道の組の項だけが残る。
$x=(\sigma;P_1,\dots,P_k)\in X$ に対し、ほかの道と頂点を共有する道 $P_i$ のうち添字 $i$ が最小のものをとる。$P_i$ を始点からたどって、ほかの道と共有する最初の頂点を $v$ とし、$v$ を通る $P_j$（$j\ne i$）のうち添字 $j$ が最小のものをとる。$i$ の最小性から $j>i$ である。$P_i$ の $a_i$ から $v$ までの部分に $P_j$ の $v$ から先を継いだ道を $P_i^{\prime}$、$P_j$ の $a_j$ から $v$ までの部分に $P_i$ の $v$ から先を継いだ道を $P_j^{\prime}$ とし、ほかの道は変えない。$P_i^{\prime}$ は $a_i$ から $b_{\sigma(j)}$ への、$P_j^{\prime}$ は $a_j$ から $b_{\sigma(i)}$ への道なので、
$$
\Phi(x):=\bigl(\sigma\circ(i\ j);\ P_1,\dots,P_i^{\prime},\dots,P_j^{\prime},\dots,P_k\bigr)
$$
は道の組であり（$(i\ j)$ は互換）、符号は $\operatorname{sgn}(\sigma\circ(i\ j))=-\operatorname{sgn}(\sigma)$ である。使う辺の多重集合は変わらないので重みは等しい。$\Phi(x)$ でも $P_i^{\prime}$ と $P_j^{\prime}$ は $v$ を共有するので $\Phi(x)\in X$ である。$\Phi(\Phi(x))=x$ であることは、$\Phi(x)$ から同じ手順で選ばれる添字と頂点が再び $i,v,j$ になることからわかる。
選ばれる添字と頂点が変わらないことの確認
$P_i^{\prime}$ と $P_j^{\prime}$ の頂点の集合の和は $P_i$ と $P_j$ の頂点の集合の和に等しく、ほかの道は変わらない。したがって添字が $i$ より小さい道は、$\Phi(x)$ でもほかの道と頂点を共有しない。$P_i^{\prime}$ は $P_j^{\prime}$ と $v$ を共有するので、最小の添字は再び $i$ である。次に、$P_i^{\prime}$ の $v$ より前の頂点 $u$ は $P_i$ の $v$ より前の頂点なので、$x$ ではどの $P_l$（$l\ne i$）にも乗っていない。$u$ が $P_j^{\prime}$ に乗るとすると、$P_j^{\prime}$ の $v$ までの部分は $P_j$ の一部なのでそこにはなく、$v$ から先は $P_i$ の $v$ より後の部分だが、$P_i$ は同じ頂点を 2 度通らないのでそこにもない。よって $P_i^{\prime}$ がほかの道と共有する最初の頂点は再び $v$ である。$P_i^{\prime},P_j^{\prime}$ 以外の道は変わらないので、$v$ を通る道の添字の集合は $x$ と同じであり、$i$ 以外で最小のものは再び $j$ である。$\Phi(x)$ で $P_i^{\prime}$ と $P_j^{\prime}$ の $v$ から先を入れ替えると $P_i,P_j$ に戻り、置換は $\sigma\circ(i\ j)\circ(i\ j)=\sigma$ に戻る。
両立するときは、交わらない道の組はすべて $\sigma=\mathrm{id}$ をもつので、後半の式が従う。$\square$
2 頂点の間の道が有限個という仮定は、$e(u,v)$ を有限和にするためだけに使う。重みを形式的冪級数環にとり、各重みの次数が正で、与えられた次数の道が有限個しかない、という形に弱めても同じ証明が通る。一方、グラフが非巡回であることは、道が同じ頂点を 2 度通らないこと（対合の確認の段）に使っており、外すと補題は成り立たない（ex-lgv-counterexamples の表）。
平面の格子路
応用でいちばんよく使うのは、平面の格子点 $\mathbb{Z}^2$ を頂点とし、各点 $(x,y)$ から東 $(x+1,y)$ と北 $(x,y+1)$ へ辺を張ったグラフである。このグラフの道を格子路という。$x+y$ は辺に沿って $1$ ずつ増えるので、このグラフは非巡回であり、2 点の間の格子路は有限個しかない。重みがすべて $1$ なら、$(x_0,y_0)$ から $(x_1,y_1)$（$x_1\ge x_0$、$y_1\ge y_0$）への格子路の個数は、東への $x_1-x_0$ 歩と北への $y_1-y_0$ 歩の並べ方の数 $\binom{(x_1-x_0)+(y_1-y_0)}{x_1-x_0}$ である（二項係数）。
格子路が高さ $y$ を通るとき、その上の頂点は横に連続した線分 $\{(x,y)\mid l_y\le x\le r_y\}$ をなし、$r_y=l_{y+1}$ である（高さ $y$ の最後の点から北へ 1 歩進むから）。
整数 $c\le d$ と整数 $\alpha_1>\alpha_2>\cdots>\alpha_k$、$\beta_1>\beta_2>\cdots>\beta_k$ をとり、$a_i=(\alpha_i,c)$、$b_j=(\beta_j,d)$ とおく。格子路のグラフ（重みは任意）において、$\mathbf a$ と $\mathbf b$ は両立する。さらに、交わらない道の組 $P_i\colon a_i\to b_i$ では、各高さ $y$（$c\le y\le d$）で $P_1,\dots,P_k$ の線分がこの順に右から左へ並ぶ。
まず次を示す：$a_i$ が $a_j$ より右にあり（$\alpha_i>\alpha_j$）、高さ $d$ の点 $b,b^{\prime}$ への格子路 $P\colon a_i\to b$ と $Q\colon a_j\to b^{\prime}$ が頂点を共有しないなら、すべての高さ $y$（$c\le y\le d$）で $P$ の線分は $Q$ の線分より真に右にある。高さ $y$ での線分を $[l_y,r_y]$（$P$）、$[l^{\prime}_y,r^{\prime}_y]$（$Q$）と書く。$y=c$ では $l_c=\alpha_i>\alpha_j=l^{\prime}_c$ で、2 つの線分は交わらないので $l_c>r^{\prime}_c$ である。高さ $y$ で $l_y>r^{\prime}_y$ なら、$l_{y+1}=r_y\ge l_y>r^{\prime}_y=l^{\prime}_{y+1}$ であり、高さ $y+1$ の線分も交わらないので $l_{y+1}>r^{\prime}_{y+1}$ である。帰納法で主張を得る。
恒等置換でない $\sigma\in S_k$ には、$i< j$ かつ $\sigma(i)>\sigma(j)$ となる $i,j$ がある。交わらない道の組 $(\sigma;P_1,\dots,P_k)$ があったとすると、$\alpha_i>\alpha_j$ なので上の主張により高さ $d$ で $P_i$ の線分は $P_j$ の線分より右にあり、終点について $\beta_{\sigma(i)}=r_d>r^{\prime}_d=\beta_{\sigma(j)}$ となる。しかし $\sigma(i)>\sigma(j)$ なので $\beta_{\sigma(i)}< \beta_{\sigma(j)}$ であり、矛盾する。後半は上の主張を $i< j$ の各組に当てればよい。$\square$
重みをすべて $1$ とし、$a_1=(1,0)$、$a_2=(0,0)$、$b_1=(2,2)$、$b_2=(1,2)$ とする。prop-lgv-planar の仮定を満たすので、thm-lgv-main により、交わらない組 $P_1\colon a_1\to b_1$、$P_2\colon a_2\to b_2$ の個数は
$$
\det\begin{pmatrix}\binom{3}{1}&\binom{2}{0}\\ \binom{4}{2}&\binom{3}{1}\end{pmatrix}=\det\begin{pmatrix}3&1\\6&3\end{pmatrix}=3
$$
である。直接数えると、$P_1$ も $P_2$ も東への 1 歩をどの高さ（$0,1,2$）で進むかで 3 通りずつある。$P_1$ のうち $(1,1)$ を通るのは高さ $1$ か $2$ で東へ進むもの、$(1,2)$ を通るのは高さ $2$ で東へ進むものである。$P_2$ が高さ $0$ で東へ進むと $(1,0)=a_1$ を通るので、どの $P_1$ とも交わる。高さ $1$ で東へ進むと $(1,1)$ と $(1,2)$ を通るので、交わらない $P_1$ は高さ $0$ で東へ進む 1 本だけである。高さ $2$ で東へ進むと、$P_1$ が通りうる点のうち $(1,2)$ だけを通るので、交わらない $P_1$ は 2 本ある。合わせて $0+1+2=3$ 組で、行列式と一致する。
Jacobi–Trudi の行列式と半標準盤
$n\ge1$ と、長さ $\ell$ の分割 $\lambda=(\lambda_1\ge\cdots\ge\lambda_\ell>0)$ を固定する（Young図形）。$\lambda$ の半標準盤とは、Young 図形の各箱に $\{1,\dots,n\}$ の元を書き込み、各行で左から右へ広義増加、各列で上から下へ狭義増加にしたものである。第 $i$ 行第 $k$ 列の数を $T(i,k)$ と書き、盤の重みを $x^T:=\prod_{i,k}x_{T(i,k)}$ とする。$h_m$ を $n$ 変数の完全対称多項式（対称多項式、$h_0=1$、$m< 0$ では $h_m=0$）とする。
$$
\sum_Tx^T=\det\bigl(h_{\lambda_i-i+j}(x_1,\dots,x_n)\bigr)_{1\le i,j\le\ell}
$$
が成り立つ。左辺の和は $\lambda$ の $\{1,\dots,n\}$ を成分とする半標準盤すべてにわたる。
格子路のグラフで、高さ $y$ の東向きの辺 $(x,y)\to(x+1,y)$ に重み $x_y$ を、北向きの辺に重み $1$ を与え、高さ $1$ から $n$ までの部分 $\mathbb{Z}\times\{1,\dots,n\}$ に制限する。始点を $a_i=(-i,1)$、終点を $b_j=(\lambda_j-j,n)$ とおく。$a_i$ から $b_j$ への格子路は東へ $m=\lambda_j-j+i$ 歩進み、高さ $y$ で東へ進む歩数を $c_y$ とすると重みは $x_1^{c_1}\cdots x_n^{c_n}$ である。$c_1+\cdots+c_n=m$ を満たす $(c_y)$ と格子路は一対一に対応するので $e(a_i,b_j)=h_{\lambda_j-j+i}$ である（$m< 0$ なら道はなく、$m=0$ なら北へ進むだけの 1 本）。$-i$ は $i$ について、$\lambda_j-j$ は $j$ について狭義減少なので、prop-lgv-planar と thm-lgv-main により
$$
\det\bigl(h_{\lambda_j-j+i}\bigr)_{i,j}=\sum_{(P_1,\dots,P_\ell)}w(P_1)\cdots w(P_\ell)
$$
であり、右辺は交わらない組 $P_i\colon a_i\to b_i$ にわたる。左辺は転置すると主張の行列式になる。
残りは、交わらない組と半標準盤の重みを保つ全単射を作ることである。$P_i$ は東へちょうど $\lambda_i$ 歩進むので、$k$ 歩目の高さを $T(i,k)$ とおくと $T(i,1)\le\cdots\le T(i,\lambda_i)$ であり、$P_i$ の重みは $x_{T(i,1)}\cdots x_{T(i,\lambda_i)}$ である。逆に広義増加の列から格子路が一意に復元される。こうして $(P_1,\dots,P_\ell)$ は、各行が広義増加の配置 $T$ と重みを保って一対一に対応する。あとは「組が交わらない」と「$T$ の各列が狭義増加」が同値であることを示せばよい。
交わらないことと列の狭義増加の同値の証明
prop-lgv-planar の証明の主張により、隣り合う $P_i$ と $P_{i+1}$ が交わらなければ、各高さで線分は $P_1,P_2,\dots,P_\ell$ の順に右から左へ真に並ぶので、全体が交わらない。よって、各 $i$ について「$P_i$ と $P_{i+1}$ が交わらない」ことと「$k=1,\dots,\lambda_{i+1}$ で $T(i,k)< T(i+1,k)$」が同値であることを示せばよい。$P_i$ の $k$ 歩目は $x=-i+k-1$ から $-i+k$ への辺なので、$P_i$ は列 $x=-i+k-1$（$1\le k\le\lambda_i+1$）を高さ $T(i,k-1)$ から $T(i,k)$ まで通る（$T(i,0):=1$、$T(i,\lambda_i+1):=n$ とおく）。同様に $P_{i+1}$ は列 $x=-i+k-1$（$0\le k\le\lambda_{i+1}$）を高さ $T(i+1,k)$ から $T(i+1,k+1)$ まで通る（$T(i+1,0):=1$、$T(i+1,\lambda_{i+1}+1):=n$）。両者が通る列は $x=-i+k-1$（$1\le k\le\lambda_{i+1}$）だけである。すべての $k\le\lambda_{i+1}$ で $T(i,k)< T(i+1,k)$ なら、その列で $P_i$ の最高点 $T(i,k)$ が $P_{i+1}$ の最低点 $T(i+1,k)$ より低いので交わらない。逆に $T(i,k)\ge T(i+1,k)$ となる最小の $k\le\lambda_{i+1}$ をとると、$k=1$ なら $T(i,0)=1\le T(i+1,1)$、$k\ge2$ なら最小性から $T(i,k-1)< T(i+1,k-1)\le T(i+1,k)$ であり、いずれも $T(i,k-1)\le T(i+1,k)\le T(i,k)$ となる。よって点 $(-i+k-1,T(i+1,k))$ を $P_i$ と $P_{i+1}$ がともに通る。
以上で、交わらない組の重みの和は半標準盤の重みの和 $\sum_Tx^T$ に等しい。$\square$
$\lambda=(2,1)$、$n=2$ とする。始点は $a_1=(-1,1)$、$a_2=(-2,1)$、終点は $b_1=(1,2)$、$b_2=(-1,2)$ である。行列式は
$$
\det\begin{pmatrix}h_2&h_3\\h_0&h_1\end{pmatrix}=h_2h_1-h_3=(x_1^2+x_1x_2+x_2^2)(x_1+x_2)-(x_1^3+x_1^2x_2+x_1x_2^2+x_2^3)=x_1^2x_2+x_1x_2^2
$$
である。半標準盤は「第 1 行 $1,1$、第 2 行 $2$」と「第 1 行 $1,2$、第 2 行 $2$」の 2 つで、重みの和は確かに $x_1^2x_2+x_1x_2^2$ になる。前者に対応する組は、$P_1$ が高さ $1$ で東へ 2 歩、$P_2$ が高さ $2$ で東へ 1 歩進む組である。$x_1=x_2=1$ とおくと交わらない組の個数 $\det\begin{pmatrix}3&4\\1&2\end{pmatrix}=2$ を得る。
Schur多項式 の定理「Jacobi–Trudi の公式」は、双交代式の商で定義した Schur 多項式 $s_\lambda$ が右辺の行列式に等しいことを述べる。これと thm-lgv-jacobi-trudi を合わせると、同じ記事の定理「半標準盤による表示」$s_\lambda=\sum_Tx^T$ が従う。逆に、半標準盤の和を定義とする流儀では、thm-lgv-jacobi-trudi が Jacobi–Trudi の公式そのものの証明になる。
Cauchy–Binet の公式
格子路でないグラフの例として、2 段の有向グラフに補題を当てると、行列の積の小行列式の公式が得られる。
$k\le m$ とし、$A$ を $R$ 成分の $k\times m$ 行列、$B$ を $m\times k$ 行列とする。$\{1,\dots,m\}$ の $k$ 元部分集合 $S$ に対し、$A$ の列を $S$ に、$B$ の行を $S$ に制限した $k$ 次正方行列を $A_S$、$B_S$ と書くと
$$
\det(AB)=\sum_{S}\det(A_S)\det(B_S)
$$
が成り立つ。和は $k$ 元部分集合 $S$ すべてにわたる。
頂点を $a_1,\dots,a_k$、$c_1,\dots,c_m$、$b_1,\dots,b_k$ とし、辺 $a_i\to c_l$ に重み $A_{il}$、辺 $c_l\to b_j$ に重み $B_{lj}$ を与える。このグラフは非巡回で、$a_i$ から $b_j$ への道は $a_i\to c_l\to b_j$（$1\le l\le m$）の $m$ 本だけなので、$e(a_i,b_j)=\sum_lA_{il}B_{lj}=(AB)_{ij}$ である。道の組 $(\sigma;P_1,\dots,P_k)$ で $P_i$ が $c_{\tau(i)}$ を通るとすると、交わらないことは $\tau$ が単射であることと同値である（$a$ と $b$ の頂点は道ごとに異なる）。$\tau$ の像を $S=\{s_1< \cdots< s_k\}$ とし、$\tau(i)=s_{\rho(i)}$ で $\rho\in S_k$ を定め、$\sigma=\pi\circ\rho$ とおくと、$\operatorname{sgn}(\sigma)=\operatorname{sgn}(\pi)\operatorname{sgn}(\rho)$ であり、
$$
\prod_iA_{i,\tau(i)}B_{\tau(i),\sigma(i)}=\prod_iA_{i,s_{\rho(i)}}\cdot\prod_rB_{s_r,\pi(r)}
$$
となる（第 2 の積で $r=\rho(i)$ とおいた）。$(\rho,\pi)$ は $S$ を固定したときの $(\tau,\sigma)$ と一対一に対応するので、thm-lgv-main により
$$
\det(AB)=\sum_S\Bigl(\sum_{\rho}\operatorname{sgn}(\rho)\prod_iA_{i,s_{\rho(i)}}\Bigr)\Bigl(\sum_{\pi}\operatorname{sgn}(\pi)\prod_rB_{s_r,\pi(r)}\Bigr)=\sum_S\det(A_S)\det(B_S)
$$
を得る。$\square$
$k>m$ のときは交わらない組が存在しない（$k$ 本の道が $m$ 個の中間の頂点を別々に通れない）ので、同じ議論で $\det(AB)=0$ がわかる。
条件を外したときの反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| def-lgv-compatible の両立性 | 格子路で $a_1=(0,0)$、$a_2=(1,0)$、$b_1=(1,1)$、$b_2=(0,1)$ | 行列式が $P_i\colon a_i\to b_i$ の交わらない組の重みの和に等しいこと |
| prop-lgv-planar の、終点が同じ高さにあること | 格子路で $a_1=(1,0)$、$a_2=(0,0)$、$b_1=(2,2)$、$b_2=(1,1)$ | 始点と終点が両立すること |
| def-lgv-path-system の非巡回性（閉路をもつグラフで、頂点を 2 度通らない道だけを数える） | $a_1\to u$、$a_2\to v$、$u\to v$、$v\to u$、$u\to b_1$、$v\to b_2$ のグラフ | thm-lgv-main の等式 |
重みはすべて $1$ とする。
1 行目．$e(a_1,b_1)=2$、$e(a_1,b_2)=1$、$e(a_2,b_1)=1$、$e(a_2,b_2)=0$（$a_2$ から左へは進めない）なので、行列式は $0-1=-1$ である。$P_1\colon a_1\to b_1$ と $P_2\colon a_2\to b_2$ の組は存在しないので、右辺は $0$ である。交わらない組は $a_1\to b_2$（北へ 1 歩）と $a_2\to b_1$（北へ 1 歩）の 1 組で、置換は互換なので符号 $-1$ をもち、thm-lgv-main の前半の式とは合う。始点と終点の並びが prop-lgv-planar の向きと逆になっている。
2 行目．$\alpha_1=1>\alpha_2=0$、$\beta_1=2>\beta_2=1$ だが、終点の高さが $2$ と $1$ で異なる。$a_1\to b_2$ を北へ 1 歩、$a_2\to b_1$ を $(0,0),(0,1),(0,2),(1,2),(2,2)$ と進むと交わらないので、互換の交わらない組がある。$\sigma=\mathrm{id}$ の交わらない組も、$a_1\to b_1$ を $(1,0),(2,0),(2,1),(2,2)$、$a_2\to b_2$ を $(0,0),(0,1),(1,1)$ とした 1 組がある（$a_2\to b_2$ のもう 1 本は $a_1$ を通る）。行列式は $\det\begin{pmatrix}3&1\\6&2\end{pmatrix}=0=1-1$ であり、thm-lgv-main の前半の式とは合うが、$\sigma=\mathrm{id}$ の組の個数 $1$ とは異なる。
3 行目．頂点を 2 度通らない道に限ると、$a_1\to b_1$ は $a_1,u,b_1$、$a_1\to b_2$ は $a_1,u,v,b_2$、$a_2\to b_2$ は $a_2,v,b_2$、$a_2\to b_1$ は $a_2,v,u,b_1$ のそれぞれ 1 本なので、行列式は $1\cdot1-1\cdot1=0$ である。一方、交わらない組は $(a_1,u,b_1)$ と $(a_2,v,b_2)$ の 1 組だけで（互換の組は $u$ と $v$ を共有する）、右辺は $1$ である。互換の組で尾を入れ替えると、同じ頂点を 2 度通る列 $a_1,u,v,u,b_1$ が現れ、道の組に戻らない。
補足
- 名前と歴史．行列式を交わらない道で表す定理は、Lindström がマトロイドの表現可能性の研究で示し、Gessel と Viennot が二項係数の行列式や平面分割・盤の数え上げに用いた（GV89 §1、§2 の Theorem 1 と Corollary 2。thm-lgv-main の証明の対合も同じ形である）。似た議論は Chaundy の平面分割の研究にもあり、Karlin と McGregor にも関連する議論がある（GV89 §2 の注意）。
- 数え上げへの応用．平面分割の数え上げや、Fibonomial 係数・Bernoulli 数などの数の組合せ的な解釈が、交わらない格子路の族に言い換えて thm-lgv-main から行列式で得られる（GV89 §1 の概観と §3 以降）。
- 形を一般にした盤．prop-lgv-planar の始点と終点の並べ方は、始点の $x$ 座標が狭義減少で高さが広義増加、終点も同様、という形に広げても両立する（GV89 §3）。これを使うと、歪んだ形の盤で各行の数に上限と下限をつけたものの母関数が行列式で表され、東向きの辺の重みの付け方を $x$ 座標に応じてずらせば、基本対称多項式 $e_m$ による行列式も同じ枠組みで扱える（GV89 §3 の Theorem 3、Corollary 4・5）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
