ポーヤの計数定理のソースを表示

[[組合せ論]]における'''ポーヤの計数定理'''（ポーヤのけいすうていり、{{lang-en-short|''Pólya enumeration theorem''}}; 数え上げ定理、枚挙定理）あるいは'''レッドフィールド&ndash;ポーヤの定理''' (''Redfield–Pólya Theorem'') は、集合への[[群作用]]の[[軌道 (群論)|軌道]]の総数を求める[[バーンサイドの補題]]の極めて一般化するものである。定理が最初に公になるのは1927年の{{仮リンク|ジョン・ハワード・レッドフィールド|en|John Howard Redfield}}によるものだが<ref>{{cite journal
 | last = Redfield
 | first = J. Howard
 | title = The theory of group-reduced distributions
 | journal = American Journal of Mathematics
 | volume = 49
 | year = 1927
 | pages = 433–455
 | doi = 10.2307/2370675
 | mr = 1506633
}}</ref>、それとは独立に[[ジョージ・ポリア]]（ポーヤ）が1937年に再発見し<ref>{{cite journal
 | last = Pólya
 | first = G.
 | authorlink = ジョージ・ポーヤ
 | title = Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
 | journal = [[Acta Mathematica]]
 | volume = 68
 | year = 1937
 | pages = 145–254
 | doi = 10.1007/BF02546665
 | mr = 1577579
}}（英訳が次の書籍の前半にある：
{{cite book
 | last1 = Pólya
 | first1 = G.
 | authorlink1 = ジョージ・ポーヤ
 | last2 = Read
 | first2 = R. C.
 | translator = Dorothee, A.
 | title = Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds
 | url = {{google books|QyjUBwAAQBAJ|plainurl=yes}}
 | publisher = Springer-Verlag
 | year = 1987
 | isbn = 0-387-96413-4
 | mr = 884155
}}）</ref>、ポーヤはその結果を多くの数え上げ問題、特に[[化合物]]の枚挙に適用して大いに普及させた。

ポーヤの計数定理は{{仮リンク|記号的組合せ論|en|symbolic combinatorics}}や{{仮リンク|組合せ論的種の理論|en|combinatorial species}}に組み込むこともできる。

== コーシーフロベニウスの補題（旧称・バーンサイドの補題）==
{{main|バーンサイドの補題}}
{''1'',''2'',…,''n''}上の置換群で、''k''個の[[軌道 (群論)|軌道]]を持つものを''G''とする。このとき、Gの置換による固定点の個数の平均は''k''である。
<math display="block">
\frac{1}{|G|}\sum_{\pi \in G} k_n (\pi) = k
</math>
上の式では、置換πによる固定点の個数を<math>k_n (\pi)</math>で表している。このことは、それぞれの点を動かさないGの要素の個数を数えることで、このことがいえる。

== ポリアの定理 I ==
集合<math>D_1</math>上の輪指数<math>P(x_1, x_2, \cdots, x_n)</math>を持つ置換群をGとする。D<sub>1</sub>からD<sub>2</sub>への[[写像]]f,gに対して<math>f(\pi(x))=g(x)</math>となる<math>\pi</math>が存在しないとき、''f''と''g''は異なるとする。このとき、''D1''から''D2''へのことなるものの個数は
<math display="block">
P(x_1, x_2, \cdots, x_n)=\frac{1}{|G|}\sum_{\pi \in G} |D_2|^{k(\pi)}
</math>
となる。

ここで、<math>|D_1|=n, |D_2|=m</math>とすると、<math>|P(x_k)|=m^n</math>となり、
<math display="block">
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)}
</math>
である。

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

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

== ポリアの定理 II ==
{{Empty section|date=2007年11月}}

== 脚注 ==
{{reflist}}

{{Combin-stub}}
{{DEFAULTSORT:ほおやのけいすうていり}}
[[Category:組合せ論]]
[[Category:数学に関する記事]]