行列式による数え上げ
非交差経路やspanning treeなどの組合せ対象を行列式に対応させ、LGV補題・行列木定理で数える。
この典型を扱う単元: 行列式による数え上げ
検索別名: LGV lemma、Matrix-Tree theorem、行列式による数え上げ、行列木定理
未知問からこの典型を見つける手掛かり
- 扱う対象
- spanning tree
- 全域木
- 有向木
- 経路
- 行列
- 使う手掛かり
- laplacian
- 木の個数
- 行列式展開
- 非交差
- 保つ不変量
- minor
- 余因子
- 符号付き置換
- 行列式
- 求めるもの
- 全域木数
- 場合の数
- 経路族の個数
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 組合せ・多項式・線形代数への変換
関連する典型
学習成果と学習単位
辺重みからLaplacianを構成し、根の行列余因子を全域木の重み付き個数へ対応させられる。有向木の向きと自己ループの扱いを説明できる。
行列式による数え上げで学ぶDAG上の経路数行列を作り、交差する経路族の符号反転と端点対応の条件から、LGVで頂点非共有経路族を数えられる。
行列式による数え上げで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC216 H「Random Robots」 公式問題主題: 行列式による数え上げ / 主タグ
- ABC253 Ex「We Love Forest」 公式問題主題: 行列式による数え上げ / 主タグ
- ABC323 G「Inversion of Tree」 公式問題主題: 行列式による数え上げ / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC216 H「Random Robots」 公式問題主題: 行列式による数え上げ / 主タグ
- ABC253 Ex「We Love Forest」 公式問題主題: 行列式による数え上げ / 主タグ
- ABC323 G「Inversion of Tree」 公式問題主題: 行列式による数え上げ / 主タグ
- ABC336 G「16 Integers」 公式問題主題: BEST定理によるEuler circuit数え上げ / 補助タグ