ポーヤの計数定理

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

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

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

詳細は「バーンサイドの補題」を参照

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

1 | G | ∑ π ∈ G k n ( π ) = k {\displaystyle {\frac {1}{|G|}}\sum _{\pi \in G}k_{n}(\pi )=k}
上の式では、置換πによる固定点の個数を k n ( π ) {\displaystyle k_{n}(\pi )} で表している。このことは、それぞれの点を動かさないGの要素の個数を数えることで、このことがいえる。

ポリアの定理 I

集合 D 1 {\displaystyle D_{1}} 上の輪指数 P ( x 1 , x 2 , ⋯ , x n ) {\displaystyle P(x_{1},x_{2},\cdots ,x_{n})} を持つ置換群をGとする。D1からD2への写像f,gに対して f ( π ( x ) ) = g ( x ) {\displaystyle f(\pi (x))=g(x)} となる π {\displaystyle \pi } が存在しないとき、fとgは異なるとする。このとき、D1からD2へのことなるものの個数は

P ( x 1 , x 2 , ⋯ , x n ) = 1 | G | ∑ π ∈ G | D 2 | k ( π ) {\displaystyle 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 {\displaystyle |D_{1}|=n,|D_{2}|=m} とすると、 | P ( x k ) | = m n {\displaystyle |P(x_{k})|=m^{n}} となり、

P ( x 1 , x 2 , ⋯ , x n ) = 1 | G | ∑ π ∈ G | D 2 | k ( π ) = 1 | G | ∑ π ∈ G m k ( π ) {\displaystyle 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 {\displaystyle |G|=24} となり、

P ( x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) = 1 24 ( x 1 6 + 6 x 1 2 x 4 + 6 x 1 2 x 2 2 + 8 x 3 2 ) {\displaystyle 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 {\displaystyle x_{1}=x_{2}=x_{3}=x_{4}=x_{5}=x_{6}=2} （2色で塗るため）なので
P ( 2 , 2 , 2 , 2 , 2 , 2 ) = 10 {\displaystyle P(2,2,2,2,2,2)=10}
となる。

ポリアの定理 II

脚注

  1. ^ Redfield, J. Howard (1927). “The theory of group-reduced distributions”. American Journal of Mathematics 49: 433–455. doi:10.2307/2370675. MR1506633. 
  2. ^ 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. https://books.google.com/books?id=QyjUBwAAQBAJ ）
  • 表示
  • 編集