ポーヤの計数定理
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/04/26 01:18 UTC 版)
組合せ論におけるポーヤの計数定理(ポーヤのけいすうていり、英: Pólya enumeration theorem; 数え上げ定理、枚挙定理)あるいはレッドフィールド–ポーヤの定理 (Redfield–Pólya Theorem) は、集合への群作用の軌道の総数を求めるバーンサイドの補題を一般化するものである。定理が最初に公になるのは1927年のジョン・ハワード・レッドフィールドによるものだが[1]、それとは独立にジョージ・ポリア(ポーヤ)が1937年に再発見し[2]、ポーヤはその結果を多くの数え上げ問題、特に化合物の枚挙に適用して大いに普及させた。
ポーヤの計数定理は記号的組合せ論や組合せ論的種の理論に組み込むこともできる。
コーシーフロベニウスの補題(旧称・バーンサイドの補題)
{1,2,…,n}上の置換群で、k個の軌道を持つものをGとする。このとき、Gの置換による固定点の個数の平均はkである。
脚注
- ^ Redfield, J. Howard (1927). “The theory of group-reduced distributions”. American Journal of Mathematics 49: 433–455. doi:10.2307/2370675. MR1506633.
- ^ Pólya, G. (1937). “Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen”. Acta Mathematica 68: 145–254. doi:10.1007/BF02546665. MR1577579.(英訳が次の書籍の前半にある: Pólya, G.; Read, R. C. Dorothee, A.訳 (1987). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. Springer-Verlag. ISBN 0-387-96413-4. MR884155)
- ポーヤの計数定理のページへのリンク