不交的等价类之并, 等价类的全体组成的集合记为 , 中的元素为 , 那么等价类的权的和就可以用 的轮换示式表示. 即 定理 3 (Polya 1937)
,
如果对
, 均取
, 则得等价类的元素个数为
证明 (见相关知识 注4) 注4
定理 3 (Polya 1937)
如果对
, 均取
, 则得等价类的元素个数为
证 设 是
中某一映射所能得到的权.记
由于同一映射类, 的权相同, 故 其权可能相同).
是由若干等价类所组成(不同的映射类,
对任意 则对任一 到
的映射
, 若 , 避有
且 则 与 有相同的权, 故若
, 可定义一个从
,
. 因此, 对固定的
即
的逆为
故 是集合
上的一个置换.
取遍 中一切元, 映射
是群 到集合 ,
均有
上的对称群 内的同态映射. 这是因为对任意的 和
记
则 是
上的一个置换群, 因此, 也是
上的一个置换群.
对 中的元素可建立两种等价关系:
: 对某一 (1)
: 对某一 (2)
由于 , 故满足 的 存在. 从而 满足 , 反之亦然,
因此这两种等价关系是同一的. 同理, 对集
的元素也有两种等价关系, 而且也是同一的.
由 Burnside 引理, 中的等价类的个数是
此处
(3)
由于 中的等价类都有权 . 因此, 用 乘(3), 然后对所有的 值求和得
由于
故
现计算
设 , 记
是 分解成轮换之积的分解式, 则由
可得
相当于(4)有 的分解式
再由(5)可得
故
(4)
(5)
例 12 用红蓝二色对正立方体 的六个面染色, 对红、蓝色赋权 (红)=, (蓝)=, 此时的轮换示式为
对正方体的两个面染色法, 如果经过群 的任意旋转, 都不能使旋转前后正方体对应的面染色相同, 则称为本质上不同的, 于是, 对正方体的面染色, 本质上不同的染色数是
对具有四个红面, 两个蓝面的本质上不同的染色数, 是多项式
中
的系数, 即 2. 如果欲求具有 个红面,
. 既有
个蓝面的染色数
.
例 13 用 2 个蓝珠, 1 个红珠, 1 个黄珠可串成多少种不同的项链?