ポリアの数え上げ定理の実装
最近ポリアの数え上げ定理の実装が欲しい場面に遭遇したのでlatexでメモを取りつつちまちま勉強していた。
↓はその時のメモ(証明は基本的に書いてない)。
ポリアの定理はある対称性のもとに色塗りをする場合の数を与えるものだが、その拡張として
- 色塗りの固定部分群が与えられた群と共役であるような色塗りの場合の数(White's lemma)
- 色を入れ替えて同じになる色塗りを同一視したときの数え上げ(De Bruijn)
などがあるようだ(こちらもそのうち勉強したい)。
さて、実装だが全通りを調べる場合は単に数式をそのままコードにすればいい。 問題は(例えば4箇所を青1赤3で塗るみたいに)使う色の数を固定する場合で、これはある多項式をかけていくときに特定の次数の項の係数だけを求めることに帰着される。 これはi番目までの多項式を乗算したときの各次数の係数に関してDPすることで求められる。
