2018-12-19から1日間の記事一覧

Lindström–Gessel–Viennot lemma

概要 格子点上で、n 組の始点と終点 $(a_1, a_2, \ldots, a_n), (b_1, b_2, \ldots, b_n)$ が定まっているとして、それらが交差しないようなパスの選び方をカウントできる定理である。($a_i$ をどの $b_j$ と対応付けるか、まで含めて。) 後にこの定理を用…