ポーヤの計数定理

組合せ論におけるポーヤの計数定理（ポーヤのけいすうていり、; 数え上げ定理、枚挙定理）あるいはレッドフィールド–ポーヤの定理 (Redfield–Pólya Theorem) は、集合への群作用の軌道の総数を求めるバーンサイドの補題を一般化するものである。定理が最初に公になるのは1927年のによるものだが、それとは独立にジョージ・ポリア（ポーヤ）が1937年に再発見し（英訳が次の書籍の前半にある：
）、ポーヤはその結果を多くの数え上げ問題、特に化合物の枚挙に適用して大いに普及させた。

ポーヤの計数定理はやに組み込むこともできる。

 コーシーフロベニウスの補題（旧称・バーンサイドの補題）

{1,2,…,n}上の置換群で、k個の軌道を持つものをGとする。このとき、Gの置換による固定点の個数の平均はkである。

上の式では、置換πによる固定点の個数をで表している。このことは、それぞれの点を動かさないGの要素の個数を数えることで、このことがいえる。

 ポリアの定理 I 
集合上の輪指数を持つ置換群をGとする。D1からD2への写像f,gに対してとなるが存在しないとき、fとgは異なるとする。このとき、D1からD2へのことなるものの個数は

となる。

ここで、とすると、となり、

である。

 例 
立方体を2色で彩色するときの仕方の数を数える。

立方体abcd-efghを考える。面abcdを1、面abefを2、面bcfgを3、面adehを4、面cdhgを5、面efghを6と名づける。このとき、となり、

ここで、（2色で塗るため）なので

となる。

 ポリアの定理 II 

 脚注 

Category:組合せ論
Category:数学に関する記事