モリアの数え上げ定理

主に競技プログラミングで用いられる「ポリアの数え上げ定理」という、回転や反転して一致するものを同じものとして数え上げる組み合わせの問題に有用な定理を示す言葉。

別名、「ポーヤの計数定理」とも呼ばれ、「ポリあ」「ポーや」の響きから

茨城県守谷市

などが連想できることから、総合してこの名をつけた。

https://gyazo.com/ad218b9ac6d305efb7ffc71bbdd3c71e

他にも、「コーシー・フロベニウスの定理」、「バーンサイドの補題」と呼ばれることもある。

以下では、定理の主張を追っていく。なお、証明はよく理解できなかったので行わない。

蟻本p.268がわかりやすいか？？？

クッキーをつくる問題設定だとイメージしやすそう

$ 2 \times 2マスの市松模様のクッキーをつくりたい。生地は$ k種類あり、それぞれの領域に選んだ生地を流し込むことができる。

この時、クッキーは何種類つくれるだろうか。ただし、回転して一致するクッキーは区別しない。（裏返して一致するものは区別する。）

お気持ち

$ k=2で考える。

普通に回転なしで計算すれば$ k^4=16通りある。

16通りを示すずを挿入

しかし、このなかにはいくつかかぶっているパターンがある。いま、下のように各パターンを定めると、それぞれのクッキーは以下のパターンに分類される。

パターンを示す図を挿入

これでは、複数の回転で被るパターンもあれば、どんな回転でも被らないパターンがあるから数えにくい。

そこで、すべての回転方法について、回転する前と後が同じようなものを数えてあげれば、今あまり被っていないパターンがたくさん出てきて、被るものも被らないものも均等な回数出てくる。

全ての回転方法について一致するものを示す図を挿入。

これを回転方法の種類数で除す。

具体的な数値で計算する。

確かに、これで一致していることが確認できる。

ポリアの数え上げ定理は、「『回転一致を同一とみなすような書き込み方の数』は、各回転に対する『その回転で不変であるような書き込み方の数』の平均をとることで求まる」という定理です。(証明はここでは行いません)

してくれ

全てのクッキーの作り方を回転の区別をあえてつけて全て均等に数え上げることで、（ありうるすべての対称操作における場合の数の和）/（対称操作の種類数）という計算式で求めることができる。