ポーヤの計数定理

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

ポーヤの計数定理はテンプレート:仮リンクやテンプレート:仮リンクに組み込むこともできる。

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

テンプレート:Main {1,2,…,n}上の置換群で、k個の軌道を持つものをGとする。このとき、Gの置換による固定点の個数の平均はkである。 $$\frac{1}{|G|}\sum _{\pi \in G}{k}_n(\pi )=k$$ 上の式では、置換πによる固定点の個数を$k_n(\pi )$で表している。このことは、それぞれの点を動かさないGの要素の個数を数えることで、このことがいえる。

ポリアの定理 I

集合$D_1$上の輪指数$P(x_1,x_2,\cdots ,x_n)$を持つ置換群をGとする。D₁からD₂への写像f,gに対して$f(\pi (x))=g(x)$となる$\pi$が存在しないとき、fとgは異なるとする。このとき、D1からD2へのことなるものの個数は $$P(x_1,x_2,\cdots ,x_n)=\frac{1}{|G|}\sum _{\pi \in G}|D_2{|}^{k(\pi )}$$ となる。

ここで、$|D_1|=n,|D_2|=m$とすると、$|P(x_k)|=m^n$となり、 $$P(x_1,x_2,\cdots ,x_n)=\frac{1}{|G|}\sum _{\pi \in G}|D_2{|}^{k(\pi )}=\frac{1}{|G|}\sum _{\pi \in G}{m}^{k(\pi )}$$ である。

例

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

立方体abcd-efghを考える。面abcdを1、面abefを2、面bcfgを3、面adehを4、面cdhgを5、面efghを6と名づける。このとき、$|G|=24$となり、 $$P(x_1,x_2,x_3,x_4,x_5,x_6)=\frac{1}{24}(x_1^6+6x_1^2{x}_4+6x_1^2{x}_2^2+8x_3^2)$$ ここで、$x_1=x_2=x_3=x_4=x_5=x_6=2$（2色で塗るため）なので $$P(2,2,2,2,2,2)=10$$ となる。