組合せ論におけるポーヤの計数定理(ポーヤのけいすうていり、; 数え上げ定理、枚挙定理)あるいはレッドフィールド–ポーヤの定理 (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

脚注