ir5 https://blog.hatena.ne.jp/ir5/ うどん記 https://ir5.hatenablog.com/ エントリのタイトルの定理について．天下一プログラマーコンテスト2013に出題された問題で知ったのでメモする． ざっくり言うと「平面グラフ上でソース頂点集合とシンク頂点集合が指定された時，vertex-disjoint なパス集合の個数を行列式で計算できるようにする」定理です．なんでも組み合わせ界隈では結構有名らしい．↓こういうのに対して ↓こういうのの個数を求める． 定理のステートメントの準備 まずは準備から．言ってることは直感的なんだけどちょっと長い．有向無閉路グラフ $G=(V,E)$ を考える．また，相異なる $2k$ 個の頂点 $s_1, s_2, ..., s_k, t_1, t_2… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fir5.hatenablog.com%2Fentry%2F20130915%2F1379171732" title="Lindström-Gessel-Viennot lemma - うどん記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://cdn-ak.f.st-hatena.com/images/fotolife/i/ir5/20130915/20130915000730.png Hatena Blog https://hatena.blog 2013-09-15 00:15:32 rich https://ir5.hatenablog.com/entry/20130915/1379171732 1.0 100%