LGV lemma [WIP]

Lindström–Gessel–Viennot lemma는 DAG의 non-intersecting path를 셀 때 사용할 수 있는 공식이다.

$G = (V, E)$에서 $2n$개의 정점 $a_{1}, \cdots, a_{n}$, $b_{1}, \cdots, b_{n}$을 생각하자. 어떤 두 path가 intersecting하다는 것은 둘 사이에 공통된 정점이 있다는 것이다. path tuple $P = (P_{1}, \cdots, P_{n})$에 대해 $P_{i}$가 $a_{i}$를 $b_{\sigma(i)}$로 보내고, $\sigma$가 순열이면 이러한 $P$를 path system이라고 하자. $P$가 non-intersecting이면 non-intersecting path system이라고 부르고, 이들의 집합을 $\mathcal{N}$이라고 쓰자.

 

Lemma. (LGV)

$p(u, v)$를 $u$에서 $v$로 가는 서로 다른 경로의 수라고 하자. 이 때 $\sum_{P \in \mathcal{N}} \mathrm{sgn}(\sigma) = \det( p(a_{i}, b_{j}) )$이다.

 

Proof. 어떤 순열 $\sigma : [n] \to [n]$과 $a_{i} \to b_{\sigma(i)}$ path $Q_{i}$를 생각하자. 가능한 경우는

 

1. $\sigma = \mathrm{id}$, non-intersecting (good)

2. intersecting

 

2번 경우에, 어떤 $i \neq j$와 intersecting하는 최소의 $i$를 찾을 수 있다. 이제 $i$와 intersecting하는 $j$중에서 최대의 $j$를 찾을 수 있다. $i$의 정의에 의해 $i < j$가 된다. 이제 둘이 만나는 정점 중 minmal한 (DAG의 partial order 기준) 정점을 $x$라고 하고, $Q_{i}$와 $Q_{j}$를 $x$ 전후로 바꿔주자. 이렇게 얻은 경로들을 $Q_{k}^{\prime}$라고 쓰자. 당연히 $k \neq i, j$에 대해서는 $Q_{k}^{\prime} = Q_{k}$이다.

이 때 $Q_{k}^{\prime}$에 동일한 변환을 가하면 다시 $Q_{k}$가 된다. 즉 이 변환은 involution인데, $Q, Q^{\prime}$에 대응되는 $\sigma$의 홀짝성은 정확히 반대가 된다. 따라서 2번의 항을 다 더하면 0이다.

 

1번의 항이 우리가 원하는 좌변의 항과 똑같기 때문에 lemma를 증명할 수 있다.

 

Plane Partition

$n \times m$ 격자의 각 칸에 $1$ 이상 $K$ 이하의 양의 정수 $a_{i, j}$ $(1 \le i \le n, 1 \le j \le m)$를 써넣되, 다음 조건을 만족하게 적고 싶다고 하자.

 

1. weakly column-increasing: $a_{i, j} \le a_{i, j+1}$

2. weakly row-increasing $a_{i, j} \le a_{i+1, j}$

 

이러한 $a_{i, j}$의 개수는 무엇일까?

잘 알려진 대응 중 하나는, 격자에서 $P_{t}$를 $t$ 이하의 칸들이라고 할 때, $P_{t}$와 $P_{t}^{C}$의 경계선이 up-right path -  row 번호가 감소하고, column 번호가 증가하는 - 를 이룬다는 사실을 이용한다. 이 경로를 $S_{1}, \cdots, S_{K-1}$이라고 생각하자. $S_{K}$는 $P_{K}$가 전체집합이기 때문에 자명하므로 신경쓰지 않아도 된다.

 

이 때 $S_{i}$와 $S_{i+1}$은 "거의 non crossing"이라고 생각할 수 있다. 이 둘은 꼭짓점을 공유할 수 있지만, 공통 간선을 가질 수 없으며 $S_{i}$는 항상 $S_{i+1}$보다 위에 있게 된다.

 

기존의 $S_{i}$들이 $(n, 0) \to (0, m)$으로 향하는 경로들이라면, $S_{i}$를 동남쪽으로 $i$칸 shift한 경로 $S_{i}^{\prime}$는 $(n+i, i) \to (i, m+i)$로 볼 수 있다. 이들은 놀랍게도 non-intersecting path system을 이룬다. DAG는 그리드에서 자연스럽게 $(i, j) \to (i-1, j), (i, j-1)$로 간선을 이어준 것으로 생각한다.

 

그리고 이 DAG에서 non-intersecting path system은 오직 $(n+i, i) \to (i, m+i)$인 경로들만 가능하다. 즉 $\sigma \neq id$ 인 경우는 가능하지 않다. 따라서 우리가 원하는 경우의 수를 LGV formula를 이용하여 바로 얻을 수 있다.

 

행렬의 원소는 $(n+i, i) \to (j, m+j)$ 경로의 수이기 때문에 $(n + m)! / (n + i - j)! (m + j - i)!$ 이 된다. 이 determinant는 닫힌 꼴로 얻을 수 있다고 하는데.. 거기까진 잘 모르겠다.

 

$\det$가 multilinear하기 때문에 각 간선, 혹은 path 하나에 변수 $w_{i, j}$를 집어넣어도 식이 동일하게 성립한다. 이를 이용해서 해결하는 문제로 https://www.acmicpc.net/problem/21265 가 있다.