ポーヤの計数定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

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

ポーヤの計数定理は記号的組合せ論英語版組合せ論的種の理論英語版に組み込むこともできる。

コーシーフロベニウスの補題(旧称・バーンサイドの補題)[編集]

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

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

ポリアの定理 I[編集]

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

となる。

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

である。


[編集]

立方体を2色で彩色するときの仕方の数を数える。 
立方体abcd-efghを考える。面abcdを1、面abefを2、面bcfgを3、面adehを4、面cdhgを5、面efghを6と名づける。このとき、|G|=24となり、

ここで、(2色で塗るため)なので

となる。

ポリアの定理 II[編集]