第四章 Pólya定理
群的概念
置换群
循环、奇循环与偶循环
Burnside引理
Pólya定理
例
母函数型的 Pólya定理
图的计数
4.1 群的概念
(1)群定义 给定集合 G和 G上的二元运算 ·,满足下列条件称为群。
(a)封闭性,若 a,b∈ G,则存在 c∈ G,使得 a·b=c.
(b)结合律成立,任意 a,b,c∈ G,有 (a·b)·c=a·(b·c).
(c)有单位元,存在 e∈ G,任意 a∈ G.a·e=e·a=a.
(d)有逆元,任意 a∈ G,存在 b∈ G,a·b=b·a=e,b=a.
由于结合律成立,(a·b)·c=a·(b·c)可记做 a·b·c.
例 证明对于 a1,a2,…,a n的乘积，结合律成立,
a·a·… ·a=a (共 n个 a相乘 ).
-1
n
4.1 群的概念
(2) 简单例子例 G={1,-1}在普通乘法下是群。
例 G={0,1,2,…,n -1}在 mod n的加法下是群,
例 二维欧氏空间所有刚体旋转 T={Ta}构成群。其中 Ta = cosa sina
-sina cosa
TbTa= cosb sinb cosa sina
-sinb cosb -sina cosa
4.1 群的概念
= cosacosb-sinasinb sinacosb+cosasinb
-sinacosb-cosasinb cosacosb-sinasinb
= cos(a+b) sin(a+b) =Ta+b
-sin(a+b) cos(a+b)
从而有 (a)封闭性 ; (b)结合律成立：
(TαTβ)Tγ = Tα(TβTγ) = TαTβTγ ; (c)有单位元：
T0 = ; (d)有逆元,Ta =T-a
= cosa -sina
sina cosa
1 0
0 1
4.1 群的概念
前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，
所以是无限群。
有限群 G的元素个数叫做群的阶,记做 |G|。
若群 G的任意二元素 a,b恒满足 ab=ba。 责称 G为交换群，或 Abel群。
设 G是群,H是 G的子集,若 H在 G原有的运算之下也是一个群,则称为 G的一个子群。
4.1 群的概念
基本性质
(a)单位元唯一 e1e2=e2=e1
(b)消去律成立 ab=ac → b=c,
ba=ca → b=c
(c)每个元的逆元唯一 aa =a a = e,
ab = ba = e,aa = ab,a = b
(d)(ab….c) =c …b a,
c …b a ab…c = e
-1 -1
-1 -1
-1 -1 -1 -1
-1 -1 -1
4.1 群的概念
(e) G有限,a∈ G,则存在最小正整数 r,使得 a = e.且 a = a,
证 设 |G|=g,则 a,a,…,a,a ∈ G,由鸽巢原理其中必有相同项。设 a =a,1≤m＜ l≤g+1,
e=a,1≤l-m≤g,令 l-m=r.则有 a =a a=e.即 a
=a,既然有正整数 r使得 a =e,其中必有最小者，不妨仍设为 r,r称为 a的阶。易见
H={a,a,…a,a =e} 在原有运算下也是一个群。
r -1 r-1
2 g g+1
m l
l-m r r-1
r-1-1 r
2 r-1 r
4.2 置换群
置换群是最重要的有限群，所有的有限群都可以用之表示。
置换,[1,n]到自身的 1-1变换。 n阶置换。
[1,n]目标集。 ( ),a1a2…a n是 [1,n]中元的一个排列。 n阶置换共有 n!个，同一置换用这样的表示可有 n!个表示法。例如 p1=( )=( ),n阶置换又可看作 [1,n]上的一元运算，一元函数。
1 2 … na
1 a2 … a n
1 2 3 43 1 2 4 3 1 4 22 3 4 1
4.2 置换群
置换乘法 P1=( ),P2=( )
P1P2=( )( )=( )
注意：既然先做 P1的置换，再做 P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。
一般而言，对 [1,n]上的 n阶置换,i[1,n]要写成
(i)P1P2,而不是 P1P2(i),(i)P有时写成 i 在上面例中,1→3→2,2→1→4,3→2→3,4→4→1,也可写 (1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1,
P2P1=( )( )=( )≠P1P2.
1 2 3 43 1 2 4
1 2 3 43 1 2 4
1 2 3 44 3 2 1
3 1 2 42 4 3 1 1 2 3 42 4 3 1
P1 P1P2 P1 P1 P2P2P2
1 2 3 44 3 2 1 4 3 2 14 2 1 3 1 2 3 44 2 3 1
4.2 置换群
(1)置换群
[1,n]上的所有 n阶置换在上面的乘法定义下是一个群。
(a)封闭性 ( )( )=( )
(b)可结合性 (( )( ))( )
=( )=( )(( )( ))
(c) 有单位元 e=( )
(d) ( ) =( )
1 2 … na
1 a2 … a n
a1 a2 … a nb
1 b2 … b n
1 2 … nb
1 b2 … b n1 2 … n
a1 a2 … a n
a1 a2 … a nb
1 b2 … b n1 2 … n
a1 a2 … a n
a1 a2 … a nb
1 b2 … b n
1 2 … nc
1 c2 … c n
b1 b2 … b nc1 c2 … c n
b1 b2 … b nc1 c2 … c n
1 2 … n1 2 … n
1 2 … na
1 a2 … a n
a1 a2 … a n1 2 … n-1
4.2 置换群
(2)例 等边三角形的运动群。
绕中心转动 120，不动，
绕对称轴翻转。
P1=( ),P2=( ),P3=( ),P4=( ),
P5=( ),P6=( )。
[1,n]上的所有置换 (共 n!个 )构成一个群，称为对称群，记做 Sn.
注意：一般说 [1,n]上的一个置换群，不一定是指 Sn.但一定是 Sn的某一个子群。
1 2 3
1 2 3
1 2 3
2 3 1
1 2 3
3 1 2
1 2 3
1 3 21 2 3
3 2 1
1 2 3
2 1 3
1
2 3
4.2 置换群
任一 n阶群同构于一个 n个文字的置换群。
设 G={a1,a2,…,a n},指定 G中任一元 ai,
任意 aj∈ G,Pi,aj→ a j ai,则 Pi是 G上的一个置换，即以 G为目标集。
Pi=( ),G的右正则表示 f：
ai→( )=Pi 。 f是单射,ai≠aj,则 Pi≠Pj
f(aiaj) = ( )
=( )( )=f(ai)f(aj)
令 P={Pi=( )|a,ai∈ G},则 P≈G
a1 a2 … a na
1ai a2ai … a naia
i aa
i a1 a2 … a n
a1(aiaj) a2(aiaj) … a n(aiaj)a
1 a2 … a na
1ai a2ai … a nai
a1 a2 … a n(a
1ai)aj (a2ai)aj … (a nai)aja
i aa
i
4.3循环、奇循环与偶循环
(a1a2…a m)=( ) 称为置换的循环表示。
于是 ( )=(14523),( )=(132)(45),
( )=(154)(2)(3).
(a1a2…a m)=(a2a3…a ma1)=…= (ama1…a m-1)有 m
种表示方法。
a1a2…a m-1ama
2 a3…a m a1
12345
43152
12345
31254
12345
52314
4.3循环、奇循环与偶循环
若两个循环无共同文字，称为不相交的，
不相交的循环相乘可交换。如 (132)(45)=
(45)(132).
若 p=(a1a2…a m),则 p =(1)(2)…(n)=e.
定理 任一置换可表成若干不相交循环的乘积。
证 对给定的任一置换 p=( ),从
1开始搜索 1→ ai1→ ai2→ ai3→…→ aik→ 1得一循环 (1 ai1 ai2… aik),若 (1 ai1 … aik)包含
n
1 2 … na
1 a2…a np p p p p p
4.3循环、奇循环与偶循环了 [1,n]的所有文字，则命题成立。否则在余下的文字中选一个，继续搜索,又得一循环。直到所有文字都属于某一循环为止。
因不相交循环可交换，故除了各个循环的顺序外，任一置换都有唯一的循环表示。
例 一副扑克牌，一分为二，交错互相插入
(洗牌 )，这样操作一次相当于一个置换 p。
i =p (i+1)/2,i=1,3,5,…,51.i/2+26,i=2,4,6,…,52,p=( ),第 i个位置被 i 号牌占据,
p
ipp
4.3循环、奇循环与偶循环
51 26...
5 3
3 2
1 1
52 52...
29 6
28 4
27 2
p = (2 27 14 33 17 9 5 3)(4 28 40 46 49 25 13 7)
(6 29 15 8 30 41 21 11)(10 31 16 34 43 22 37 19)
(12 32 42 47 24 38 45 23)(18 35)
(20 36 44 48 50 51 26 39)(52)
p = e
2阶循环叫做对换。
8
4.3循环、奇循环与偶循环
定理 任一循环都可以表示为对换的积。
(1 2 … n)=(1 2)(1 3)…(1 n)=(2 3)(2 4)…(2 n)(2 1)
表示不唯一。 sgn(p)∈ {1,-1}.
(1)sgn(p) ∏
(2)sgn(pq)=sgn(p)sgn(q)
(3)sgn((i,i+1))=-1,p=(i,i+1)
(4)sgn((l k))=-1 奇数个邻位对换。
故任一置换表示成对换的个数的奇偶性是唯一的置换分成两大类：奇置换与偶置换。循环长度减 1的奇偶性即置换奇偶性。
△= i - j
i-j
p p
i>j
4.3循环、奇循环与偶循环
例 0表示空格，任一变动都是与 0做相邻的对换。
p=(0)(1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8)
奇置换。 0从右下角出发回到右下角，水平方向上，垂直方向上都做了偶数次对换。一个奇置换不会等于一个偶置换。
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 0
4.3循环、奇循环与偶循环
定理 Sn中所有偶置换构成一阶为 (n!)/2的子群称为交错群，记做 An,
证 (1)封闭性
(2)单位元
(3)逆元 (i k) = (i k)
设 p = (i1 j1)(i2 j2)…(i i ji),则 p = (ii ji)…(i 1 j1)
令 Bn=Sn-An,|Bn|+|An|=n!,
则 (i j) Bn包含于 An |Bn|≤|An|，
(i j) Bn包含于 An |An|≤|Bn|
∴ |An|=|Bn|=(n!)/2
-1
4.4 Burnside引理
(1)共轭类先观察 S3,A3,S4,A4,以增加感性认识。
S3={(1)(2)(3),(23),(13),(12),(123),(132)},
A3={(1)(2)(3),(123),(132)},
S4={(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),
(123),(124),(132),(134),(142),(143),(234),(243),
(1234),(1243),(1324),(1342),(1423),(1432),
(12)(34),(13)(24),(14)(23)},
A4={(1)(2)(3)(4),(123),(124),(132),(134),(142),
(143),(234),(243),(12)(34),(13)(24),(14)(23)}.
(1234)=(12)(13)(14)
4.4 Burnside引理
Sn中 P的循环格式 (1) (2) …( n),∑kCk=
n
Sn中有相同格式的置换全体构成一个共轭类。
定理 1 Sn中属 (1) (2) …( n) 共轭类的元的个数为
C1 C2 Cn
n
k=1
C1 C2 Cn
n！
C1!C2!…C n!1 2 … n C1 C2 Cn
一般来说,Sn中任意一个置换 P分解成若干不相交的循环乘积,
P=(a1a2…ak 1) (b1b2…bk 2)… (c1c2…ck m)
其中 k1+k2+…+k m=n
这里 k循环出现的次数为 ck,用 (k)ck表示,
例如,(1)(23)(4567)属于格 (1)1(2)1(3)0(4)1(5)0(6)0(7)0
而 (1)(23)(45)(67)属于格 (1)1(2)3(3)0(4)0(5)0(6)0(7)0
4.4 Burnside引理
证 (1) (2) …( n) 即C1 C2 Cn
(·)…(·)(··)…(··)… (·…·)…(·…·)
_∧ _
/ \
1个
_∧ _
/ \
2个
____∧ ____
/ \
n个
\______ ______/
\/ C
1个
\________ ________/
\/ C
2个
\________ ________/
\/ C
n个一个长度为 k的循环有 k种表示,Ck个长度为 k的循环有 Ck!k 种表示,1,2,…,n的全排列共有 n!个，给定一个排列，装入格式得一置换，除以前面的重复度得
n!/(C1!C2!…C n!1 2 … n ) 个不同的置换,
Ck
C1 C2 Cn
4.4 Burnside引理
例 1 S4中 (2) 共轭类有 4!/(2!2 )=3
(1) (3) 共轭类有 4!/(C1!C3!1 3 )=8
(1) (2) 共轭类有 4!/(C1!C2!1 2 )=6
(2)k不动置换类设 G是 [1,n]上的一个置换群。 G≤Sn,
K∈ [1,n]G中使 k保持不变的置换全体，
称为 k不动置换类，记做 Zk.
2
C1 C3
C1 C2
1 1
2 1
2
4.4 Burnside引理
定理 置换群 G的 k不动置换类 Zk是 G的一个子群。
封闭性,k→k→k,k k.
结合性：自然。
有单位元,G的单位元属于 Zk.
有逆元,P∈ Zk,k→k,则 k→k,P ∈ Zk.
∴ Zk≤G.
P1 P2 P1P2
P P-1
4.4 Burnside引理
(3)等价类 举一个例子。
G={(1)(2)(3)(4),(12),(34),(12)(34)}.在 G下，
1变 2,3变 4，但 1不变 3。 Z1=Z2={e,(34)},
Z3=Z4={e,(12)}.对于 A4,
Z1={e,(234),(243)},Z2={e,(134),(143)}
Z3={e,(124),(142)},Z4={e,(123),(132)}
一般 [1,n]上 G将 [1,n]分成若干等价类，满足等价类的 3个条件,(a)自反性 ;(b)对称性 ;(c)传递性。
4.4 Burnside引理
一个由 G定义的关系 k：
若存在 p∈ G,使得 k→j 则称 kRj.显然 kRk；
kRj则 jRk； kRj,jRl则 kRl。 R是 [1,n]上的一个等价关系。将 [1,n]划分成若干等价类。
含目标集元素 k的在 G作用下的等价类也称为含 k的轨道。
p
4.4 Burnside引理
定理 设 G是 [1,n]上的一个置换群,Ek是 [1,n]在 G
的作用下包含 k的等价类,Zk是 k不动置换类。
有 |Ek||Zk|=|G|,
证 设 |Ek|=l,Ek={a1(=k),a2,…,a l} k=a1→a i,i=1,2,…,l,
P={p1,p2,…,p l}令 Gi=ZkPi,i=1,2,…,l.
Gi包含于 G(G关于 Zk的陪集分解 )i≠j,Gi∩Gj=Φ,
G1+G2+…+G l包含于 G,另一方面，任意 P∈ G,
k→a j→k PPj ∈ Zk,P∈ ZkPj=Gj.
∴ G包含于 G1+…+G l.从而,G=G1+G2+…+G l.
|G|=|G1|+|G2|+…+|G l|=|Zk|·l= |Zk|·|Ek|
Pi
· · ·
· ·
-1Pj-1P
4.4 Burnside引理
(4)Burnside引理设 G={a1,a2,…a g}是目标集 [1,n]上的置换群。每个置换都写成不相交循环的乘积。
G将 [1,n]换分成 l个等价类。 c1ak是在置换
ak的作用下不动点的个数，也就是长度为
1的循环的个数。
Burnside引理
l=[c1(a1)+c1(a2)+…+c 1(ag)]/|G|
4.4 Burnside引理
例如,G={e,(12),(34),(12)(34)},
c1(a1)=4,c1(a2)=2,c1(a3)=2,c1(a4)=0.
l=[4+2+2+0]/4=2,以本例列表分析：
1 2 3 4 c1(aj)
(1)(2)(3)(4) 1 1 1 1 4 (1)
(12)(3)(4) 0 0 1 1 2 (1) (2)
(1)(2)(34) 1 1 0 0 2 (1) (2)
(12)(34) 0 0 0 0 0 (2)
|Zk| → 2 2 2 2 8
Sjk k
aj
4
2 1
2 1
2
4.4 Burnside引理
Sjk=
对第 j行求和得 c1(aj),对第 k列求和得 |Zk|
表中元素的总和 =∑∑Sjk=∑|Zk|=∑c1(aj).
一般而言，与上表相仿，有下页表格，
其中 Sjk=
1,k =k,
0,k ≠k.
aj
aj
g
j=1
g
j=1
n
k=1
n
k=1
1,k =k,
0,k ≠k.
aj
aj
4.4 Burnside引理
Sjk k
aj 1 2 … n c1(aj)
a1 S11 S12 … S 1n c1(a1)
a2 S21 S22 … S 2n c1(a2)
… … … …
ag Sg1 Sg2 … Sg n c1(ag)
|Zk| |Z1||Z2| … |Z1| ∑|Zk|=∑c1(aj).g
j=1
n
k=1
∵ ∑Sjk=c1(aj),∑Sjk=|Zk|,设在 G作用下，
[1,n]分成 l个等价类。 [1,n]=E1+E2+…+E l.
g
j=1
n
k=1
4.4 Burnside引理
若 j,I同属一个等价类，则 Ei=Ej,|Ei|=|Ej|
因 |Ei||Zi|=|G|,故 |Zi|=|Zj|,∑|Zi|=|Ej||Zj|
∴ ∑|Zk|=∑∑|Zk|=∑|Ei||Zi|=∑|G|=l|G|
∴ l= ∑|Zk|= ∑c1(aj).
i∈ Ej
g
j=1
n
k=1
n
k=1
1
|G|
1
|G|
l
i=1
l
i=1
l
i=1i∈ Ej
4.4 Burnside引理
例 2 一正方形分成 4格,2着色，有多少种方案？图象：看上去不同的图形。方案：
经过转动相同的图象算同一方案。图象数总是大于方案数。
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
4.4 Burnside引理
不动,p1=(1)(2)…(16)
逆时针转 90,p2=(1)(2)(3 4 5 6)(7 8 9 10)
(11 12)(13 14 15 16)
顺时针转 90,p3=(1)(2)(6 5 4 3)(10 9 8 7)
(11 12)(16 15 14 13)
转 180,p4=(1)(2)(3 5)(4 6)(7 9)(8 10)
(11 12) (13 15)(14 16)
(16+2+2+4)/4=6(种方案 )
。
。
。
4.5 Pólya定理
设 Ω=[1,n],M={S1,S2,…S m}是 m种颜色的集合，对 Ω中的元素用 M中的颜色着色，
得到的图象集合用 M 表示,|M |=m,每个中的元素都有 m种着色可能,n个元的着色有 m 种可能。即共有 m 个图象。
设 G是以 Ω为目标记得置换群，是某一转动群 R的表示。 G是以 M 为目标记得置换群，是同一转动群 R的表示。
Ω Ω
Ω
n n
n
4.5 Pólya定理
G≌ R,G≌ R,G≌ G
一个着色图象在 G的作用下变为另一个图象，则这两个图象属于同一方案。
Pólya定理 设 G={P1,P2,…,P g}是 Ω上的一个置换群,C(Pk)是置换 Pk的循环的个数，
用 M中的颜色对 Ω中的元着色，着色方案数为 l=—[m +m +…+m ].C(P1) C(P2) C(Pg)1 |G|
4.5 Pólya定理
f:Ω→M,G 是作用在图象集合 M 上的置换群。对于 P∈ G,P=,k=1,2,…,n
T,P→P,P=,i=1,2,…,m,
T:G→G f i(k)=fi(k ),i=1,2,…,m,k=1,…,n,
P称为由 P诱导出的 M 上的置换。
G={P1,…,P g},G={P1,P2,…,P g}
T是 G到 G的同构映射。 C1(Pi)=m
Ω
k
kp
fi
fi
p n
△
_p
n
Ω
C(Pi)
4.5 Pólya定理
在 Pi作用下 M 中的不动图象的个数
C1(Pi)=m,C(Pi)表示 Pi的循环的个数，
即同一循环中的元素都着同一种颜色的图象在 Pi的作用下保持不变。
对应于 P∈ G,有 P∈ G,P是 M (图象集 )上的一个置换。现在要计算的也就是图象集在 G作用下的等价类的个数。下面对前例进行分析，然后推导到一般。
Ω
C(Pi)
Ω
4.5 Pólya定理
P1=(1)(2)(3)(4),P1=(1)(2)…(16)
P2=(4321),P2=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)
P3=(1234),P3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)
P4=(13)(24),P4=(1)(2)(35)(46)(79)(8 10)(11)(12)(13 15)(14 16)
C(P1)=4,C1(P1)=16=2
C(P2)=1,C1(P2)=2=2
C(P3)=1,C1(P3)=2=2
C(P4)=2,C1(P4)=4=2
求着色的方案数也即求图象的等价类个数。按
Burside定理，求等价类的个数归结为每个置换下的不动点 (不动图象 )的个数。
C(P1)
C(P2)
C(P3)
C(P4)
2 1
3 4
4.5 Pólya定理
证 对 Ω的 n个目标用 m种颜色着色的图象集为 M |M |=|M| =m
G的每一个元 Pi是 Ω上的一个置换，也对应了 M 上的一个置换 Pi,这样 G≌ G,T:Pi←→ Pi
在 Pi的作用下不动图象的个数 C1(Pi)等于 Pi
的同一循环中的目标都着相同色的选择的个数。即 C1(Pi)=m 。 因而在 G的作用下，
M (图象 )的等价类的个数。
l=—[C1(P1)+…+C 1(Pg)]=—[m +m +…+m ],
Ω |Ω| Ω
Ω
n
C(Pi)
Ω
C(P1) C(P2) C(Pg)1
|G|
1
|G|
4.6 举例
例 1 等边三角形的 3个顶点用红，兰，绿 3
着色，有多少种方案？
解 在 3维空间考虑,3顶点的置换群 S3.
(3),2个；
(1) (2),3个；
(1),1个；
l = (2·3 +3·3 +3 )/6=10
1
3
1 1
1 2 3
4.6 举例
例 2 甲烷 CH4的 4个键任意用 H,Cl,CH3,
C2H5 连接，有多少种方案？
解 CH4的结构是一个正 4面体,C原子居于正 4面体的中心。正 4面体的转动群按转动轴分类,顶点 -对面的中心,(1)(3) 8个；
棱中 -棱中,(2) 3个； 不动,(1) 1个；
6条棱,每条棱看作一有向边，正向重合与反向重合共 6·2=12个位置，故转动群的群元有 12个。 l=[11·4 +4 ]/12=[44+64]/3=36。2 4
4.6 举例
例 3 3个输入端一个输出端的布尔电路有多少种实质上不同的结构？
解 3个变量的布尔函数形式上有 2 =256个,但有的只是输入端的顺序不同,输入端的变换群是 S3。
输入端的电平取值共有 000~111计 8种。 输出
f,S3→H S3≌ H
Pj→h j= i=0~7
P1=(1)(2)(3),h1=
(1) (1) 1个 ;(3) (1) (3) 2个 ;(1) (2) (1) (2) 3个 ;
结构总数为 [2 +2·2 +3·2 ]/6=80
a1 a2 a3
a1 a2 a3
(i) (i) (i)
(i) (i) (i)
pj pj pj
000 001 010 011 100 101 110 111
000 001 010 011 100 101 110 111
3 8 1 2 2 1 1 4 2
4.6 举例
例 4 正 6面体的 6个面分别用红，蓝两种颜色着色，有多少方案？
正 6面体的转动群用面的置换表示：
面心 -面心 ± 90 (1) (4) 6个
180 (1) (2) 3个 顶点 -顶点
± 120 (3) 8个 棱中 -棱中
180 (2) 6个不动
(1) 1个 [12·2 +3·2 +8·2 +2 ]/24=10
。
。
。
。
2
2 2
2
3
6
3 4 2 6
4.6 举例
例 5 用 2种颜色给正 6面体的 8个顶点着色，
有多少方案？
解 用顶点的置换表示：
面心 -面心 ± 90 (4) 6个
180 (2) 3个 顶点 -顶点
± 120 (1) (3) 8个 棱中 -棱中
180 (2) 6个不动
(1) 1个 [17·2 +6·2
+2 ]/24=[34+3+32]/3=23
。
。
。
。
2
4
2 2
4
8
4 2 8
4.6 举例
例 6 在正 6面体的每个面上任意做一条对角线，
有多少方案？
解 在每个面上做一条对角线的方式有 2种，可参考面的 2着色问题。但面心 -面心的转动轴转
± 90 时，无不动图象。除此之外，都可比照面的 2着色。所求方案数：
不动 (1) 1个 2
面心 -面心 ± 90 (1) (4) 6个 无不动图象 0
180 (1) (2) 3个 3·2
顶点 -顶点 ± 120 (3) 8个 8·2
棱中 -棱中 180 (2) 6个 6·2
[2 +0+ 3·2 +8·2 +6·2 ]/24=[8+6+4+6]/3=8
。
。
。
。
6
2
2 2
2
3
6 4 2 3
6
4
2
3
4.6 举例
例 7 骰子的 6个面分别有 1,…,6 点，有多少种不同的方案？
解 1) 6!个图象的目标集,只有单位元有 6!
个不动点 (图象 )其他 23个群元不动点。由
Burnside引理有 [C1(e)]/24=6!/24=30个方案。 C1(p1)=C1(p2)=…=C 1(p23)=0
2) 2点,3点,6点各有两种取向，
1点,4点,5点各有一种取向，
故应有 30·2=240种方案。
· ·· ·· ··· ······ ··· ···
· ···· · ·· ·
4.6 举例
为了解决正多面体及一些对称对面体的计算问题介绍下面的定理。
定义 凸多面体与一个顶点相关的面角之和与 360 的差称为该顶点的欠角。
定理 凸多面体各顶点欠角的和为 720 (用欧拉定理证 )
。
。
4.6 举例
用正 5边形搭成的正多面体,
(5-2)·180/5=108,360 -3·108 =36。
720 /36 =20(个顶点 )
一个顶点 3条棱，重复度为 2,20·3/2=30条棱一个顶点相关 3个面,重复度为 5,20·3/5=12个面
用正 3角形搭成的面最多的正多面体,
360 -5·60 =60 。 720 /60 =12(个顶点 )
一个顶点关联 5条棱,重复度为 2,12·5/2=30条棱。
一个顶点关联 5个面,重复度为 3,12·5/3=20个面
。 。 。 。
。 。
。 。 。 。 。
4.6 举例
足球：
欠角 =360 –(108 +2·120 )=12
720 /12 =60(个顶点 ) 60·3/2=90(条棱 )
60/5=12(个 5边形 ) 60·2/6=20(个 6边形 )
(正 20面体砍去 12个顶点 )
。 。 。 。
4.7 母函数型式的 Pólya定理
l=—[∑m ] 目标集 [1,n]
m种颜色,b1,b2,…,b m m 用
(b1+b2+…+b m) (b1+b2+…+b m) …
(b1+b2+…+b m) 代替。 P(b1,b2,…,b m)
以 b1,b2,…,b m为复元的 n次对称多项式。
令 Sk=(b1+b2+…+b m)
m ~ S1 S2 …S n
P(b1,b2,…,b m)=—∑∏Sj
∑kCk(pi)=n
1
|G|
g
C(Pi)
i=1
C(Pi) C1(Pi) C2(Pi)2 2 2
n n n C(Pi)
k k k
C(Pi) C1(Pi) C2(Pi) Cn(Pi)
Cj(Pi)1
|G|
g n
i=1 j=1
4.7 母函数型式的 Pólya定理
例 1 有 3种不同颜色的珠子，串成 4颗珠子的项链，有哪些方案？
解 正 4边形的运动群绕心转 ± 90 (4) 2个
180 (2) 1个 绕轴翻转
(2) 2个
(1) (2) 2个 不动
(1) 1个
。
。
1
2
2
2
4
4.7 母函数型式的 Pólya定理
P(b,g,r)=[(b+g+r) +2(b +g +r ) +3(b +g +r )
+2(b+g+r) (b +g +r )]/8
=b +g +r +b g+b r+bg +br +g r+gr
+2b g +2b r +2g r +2b gr+2bg r+2bgr
例 2 4颗红色珠子嵌在正 6面体的 4个顶点上，有多少方案？
解 相当于对顶点 2着色。无珠设 b,
(1) 1个 ; (4) 6个 ; (2) 9个 ; (1) (3) 8个 ;
p=[(b+r) +6(b +r ) +9(b +r ) +8(b+r) (b +r ) ]/24
4 4 4 4 2 2 2 2
2 2 2 2
4 4 4 3 3 3 3 3 3
2 2 2 2 2 2 2 2 2
8 4 4 2 2 2 4 2 3 3 2
4.7 母函数型式的 Pólya定理
b r 的系数,—[——+6·2+9·——+8·2]=71 8!24 4!4! 4!2!2!4 4
4.8 图的计数
例 1 4个顶点的图，对完全图的边的 2着色
S4的每个置换对应 6条边的集上的一个置换
(1) (1) 1个
(4) (2) (4) 6个
(2) (1) (2) 3个
(1) (2) (1) (2) 6个
(1) (3) (3) 8个
P(x,y) = —[(x+y) +9(x+y) (x +y ) +8(x +y )
+6(x+y) (x +y ) ]
1
24
6 2 2 2 2 3 3 2
2 2 2 2
4
1
2
2
6
1
2 2
2 2
2
4.8 图的计数
=x +x y+2x y +3x y +2x y +xy +y6 5 4 2 3 3 2 4 5 6
4.8 图的计数
例 2 求 4个顶点的不同构的有向图的个数。
解 顶点置换 有向边置换
(1) (1) 1个
(1) (2) (1) (2) 6个
(2) (2) 3个
(1) (3) (3) 8个
(4) (4) 6个
P(x,y) = —[(x+y) +6(x+y) (x +y ) +3(x +y )
+8(x +y ) +6(x +y ) ]
4
2
2
12
2 5
6
4
3
12 2 2 2 5 2 2 6
3 3 4 4 4 3
1
24
4.8 图的计数
x y 的系数,—[——+6(1+—)+3—+0+0]=51 12! 5! 6!24 2!10! 4! 5!2 10
群的概念
置换群
循环、奇循环与偶循环
Burnside引理
Pólya定理
例
母函数型的 Pólya定理
图的计数
4.1 群的概念
(1)群定义 给定集合 G和 G上的二元运算 ·,满足下列条件称为群。
(a)封闭性,若 a,b∈ G,则存在 c∈ G,使得 a·b=c.
(b)结合律成立,任意 a,b,c∈ G,有 (a·b)·c=a·(b·c).
(c)有单位元,存在 e∈ G,任意 a∈ G.a·e=e·a=a.
(d)有逆元,任意 a∈ G,存在 b∈ G,a·b=b·a=e,b=a.
由于结合律成立,(a·b)·c=a·(b·c)可记做 a·b·c.
例 证明对于 a1,a2,…,a n的乘积，结合律成立,
a·a·… ·a=a (共 n个 a相乘 ).
-1
n
4.1 群的概念
(2) 简单例子例 G={1,-1}在普通乘法下是群。
例 G={0,1,2,…,n -1}在 mod n的加法下是群,
例 二维欧氏空间所有刚体旋转 T={Ta}构成群。其中 Ta = cosa sina
-sina cosa
TbTa= cosb sinb cosa sina
-sinb cosb -sina cosa
4.1 群的概念
= cosacosb-sinasinb sinacosb+cosasinb
-sinacosb-cosasinb cosacosb-sinasinb
= cos(a+b) sin(a+b) =Ta+b
-sin(a+b) cos(a+b)
从而有 (a)封闭性 ; (b)结合律成立：
(TαTβ)Tγ = Tα(TβTγ) = TαTβTγ ; (c)有单位元：
T0 = ; (d)有逆元,Ta =T-a
= cosa -sina
sina cosa
1 0
0 1
4.1 群的概念
前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，
所以是无限群。
有限群 G的元素个数叫做群的阶,记做 |G|。
若群 G的任意二元素 a,b恒满足 ab=ba。 责称 G为交换群，或 Abel群。
设 G是群,H是 G的子集,若 H在 G原有的运算之下也是一个群,则称为 G的一个子群。
4.1 群的概念
基本性质
(a)单位元唯一 e1e2=e2=e1
(b)消去律成立 ab=ac → b=c,
ba=ca → b=c
(c)每个元的逆元唯一 aa =a a = e,
ab = ba = e,aa = ab,a = b
(d)(ab….c) =c …b a,
c …b a ab…c = e
-1 -1
-1 -1
-1 -1 -1 -1
-1 -1 -1
4.1 群的概念
(e) G有限,a∈ G,则存在最小正整数 r,使得 a = e.且 a = a,
证 设 |G|=g,则 a,a,…,a,a ∈ G,由鸽巢原理其中必有相同项。设 a =a,1≤m＜ l≤g+1,
e=a,1≤l-m≤g,令 l-m=r.则有 a =a a=e.即 a
=a,既然有正整数 r使得 a =e,其中必有最小者，不妨仍设为 r,r称为 a的阶。易见
H={a,a,…a,a =e} 在原有运算下也是一个群。
r -1 r-1
2 g g+1
m l
l-m r r-1
r-1-1 r
2 r-1 r
4.2 置换群
置换群是最重要的有限群，所有的有限群都可以用之表示。
置换,[1,n]到自身的 1-1变换。 n阶置换。
[1,n]目标集。 ( ),a1a2…a n是 [1,n]中元的一个排列。 n阶置换共有 n!个，同一置换用这样的表示可有 n!个表示法。例如 p1=( )=( ),n阶置换又可看作 [1,n]上的一元运算，一元函数。
1 2 … na
1 a2 … a n
1 2 3 43 1 2 4 3 1 4 22 3 4 1
4.2 置换群
置换乘法 P1=( ),P2=( )
P1P2=( )( )=( )
注意：既然先做 P1的置换，再做 P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。
一般而言，对 [1,n]上的 n阶置换,i[1,n]要写成
(i)P1P2,而不是 P1P2(i),(i)P有时写成 i 在上面例中,1→3→2,2→1→4,3→2→3,4→4→1,也可写 (1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1,
P2P1=( )( )=( )≠P1P2.
1 2 3 43 1 2 4
1 2 3 43 1 2 4
1 2 3 44 3 2 1
3 1 2 42 4 3 1 1 2 3 42 4 3 1
P1 P1P2 P1 P1 P2P2P2
1 2 3 44 3 2 1 4 3 2 14 2 1 3 1 2 3 44 2 3 1
4.2 置换群
(1)置换群
[1,n]上的所有 n阶置换在上面的乘法定义下是一个群。
(a)封闭性 ( )( )=( )
(b)可结合性 (( )( ))( )
=( )=( )(( )( ))
(c) 有单位元 e=( )
(d) ( ) =( )
1 2 … na
1 a2 … a n
a1 a2 … a nb
1 b2 … b n
1 2 … nb
1 b2 … b n1 2 … n
a1 a2 … a n
a1 a2 … a nb
1 b2 … b n1 2 … n
a1 a2 … a n
a1 a2 … a nb
1 b2 … b n
1 2 … nc
1 c2 … c n
b1 b2 … b nc1 c2 … c n
b1 b2 … b nc1 c2 … c n
1 2 … n1 2 … n
1 2 … na
1 a2 … a n
a1 a2 … a n1 2 … n-1
4.2 置换群
(2)例 等边三角形的运动群。
绕中心转动 120，不动，
绕对称轴翻转。
P1=( ),P2=( ),P3=( ),P4=( ),
P5=( ),P6=( )。
[1,n]上的所有置换 (共 n!个 )构成一个群，称为对称群，记做 Sn.
注意：一般说 [1,n]上的一个置换群，不一定是指 Sn.但一定是 Sn的某一个子群。
1 2 3
1 2 3
1 2 3
2 3 1
1 2 3
3 1 2
1 2 3
1 3 21 2 3
3 2 1
1 2 3
2 1 3
1
2 3
4.2 置换群
任一 n阶群同构于一个 n个文字的置换群。
设 G={a1,a2,…,a n},指定 G中任一元 ai,
任意 aj∈ G,Pi,aj→ a j ai,则 Pi是 G上的一个置换，即以 G为目标集。
Pi=( ),G的右正则表示 f：
ai→( )=Pi 。 f是单射,ai≠aj,则 Pi≠Pj
f(aiaj) = ( )
=( )( )=f(ai)f(aj)
令 P={Pi=( )|a,ai∈ G},则 P≈G
a1 a2 … a na
1ai a2ai … a naia
i aa
i a1 a2 … a n
a1(aiaj) a2(aiaj) … a n(aiaj)a
1 a2 … a na
1ai a2ai … a nai
a1 a2 … a n(a
1ai)aj (a2ai)aj … (a nai)aja
i aa
i
4.3循环、奇循环与偶循环
(a1a2…a m)=( ) 称为置换的循环表示。
于是 ( )=(14523),( )=(132)(45),
( )=(154)(2)(3).
(a1a2…a m)=(a2a3…a ma1)=…= (ama1…a m-1)有 m
种表示方法。
a1a2…a m-1ama
2 a3…a m a1
12345
43152
12345
31254
12345
52314
4.3循环、奇循环与偶循环
若两个循环无共同文字，称为不相交的，
不相交的循环相乘可交换。如 (132)(45)=
(45)(132).
若 p=(a1a2…a m),则 p =(1)(2)…(n)=e.
定理 任一置换可表成若干不相交循环的乘积。
证 对给定的任一置换 p=( ),从
1开始搜索 1→ ai1→ ai2→ ai3→…→ aik→ 1得一循环 (1 ai1 ai2… aik),若 (1 ai1 … aik)包含
n
1 2 … na
1 a2…a np p p p p p
4.3循环、奇循环与偶循环了 [1,n]的所有文字，则命题成立。否则在余下的文字中选一个，继续搜索,又得一循环。直到所有文字都属于某一循环为止。
因不相交循环可交换，故除了各个循环的顺序外，任一置换都有唯一的循环表示。
例 一副扑克牌，一分为二，交错互相插入
(洗牌 )，这样操作一次相当于一个置换 p。
i =p (i+1)/2,i=1,3,5,…,51.i/2+26,i=2,4,6,…,52,p=( ),第 i个位置被 i 号牌占据,
p
ipp
4.3循环、奇循环与偶循环
51 26...
5 3
3 2
1 1
52 52...
29 6
28 4
27 2
p = (2 27 14 33 17 9 5 3)(4 28 40 46 49 25 13 7)
(6 29 15 8 30 41 21 11)(10 31 16 34 43 22 37 19)
(12 32 42 47 24 38 45 23)(18 35)
(20 36 44 48 50 51 26 39)(52)
p = e
2阶循环叫做对换。
8
4.3循环、奇循环与偶循环
定理 任一循环都可以表示为对换的积。
(1 2 … n)=(1 2)(1 3)…(1 n)=(2 3)(2 4)…(2 n)(2 1)
表示不唯一。 sgn(p)∈ {1,-1}.
(1)sgn(p) ∏
(2)sgn(pq)=sgn(p)sgn(q)
(3)sgn((i,i+1))=-1,p=(i,i+1)
(4)sgn((l k))=-1 奇数个邻位对换。
故任一置换表示成对换的个数的奇偶性是唯一的置换分成两大类：奇置换与偶置换。循环长度减 1的奇偶性即置换奇偶性。
△= i - j
i-j
p p
i>j
4.3循环、奇循环与偶循环
例 0表示空格，任一变动都是与 0做相邻的对换。
p=(0)(1 15)(2 14)(3 13)(4 12)(5 11)(6 10)(7 9)(8)
奇置换。 0从右下角出发回到右下角，水平方向上，垂直方向上都做了偶数次对换。一个奇置换不会等于一个偶置换。
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
15 14 13 12
11 10 9 8
7 6 5 4
3 2 1 0
4.3循环、奇循环与偶循环
定理 Sn中所有偶置换构成一阶为 (n!)/2的子群称为交错群，记做 An,
证 (1)封闭性
(2)单位元
(3)逆元 (i k) = (i k)
设 p = (i1 j1)(i2 j2)…(i i ji),则 p = (ii ji)…(i 1 j1)
令 Bn=Sn-An,|Bn|+|An|=n!,
则 (i j) Bn包含于 An |Bn|≤|An|，
(i j) Bn包含于 An |An|≤|Bn|
∴ |An|=|Bn|=(n!)/2
-1
4.4 Burnside引理
(1)共轭类先观察 S3,A3,S4,A4,以增加感性认识。
S3={(1)(2)(3),(23),(13),(12),(123),(132)},
A3={(1)(2)(3),(123),(132)},
S4={(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),
(123),(124),(132),(134),(142),(143),(234),(243),
(1234),(1243),(1324),(1342),(1423),(1432),
(12)(34),(13)(24),(14)(23)},
A4={(1)(2)(3)(4),(123),(124),(132),(134),(142),
(143),(234),(243),(12)(34),(13)(24),(14)(23)}.
(1234)=(12)(13)(14)
4.4 Burnside引理
Sn中 P的循环格式 (1) (2) …( n),∑kCk=
n
Sn中有相同格式的置换全体构成一个共轭类。
定理 1 Sn中属 (1) (2) …( n) 共轭类的元的个数为
C1 C2 Cn
n
k=1
C1 C2 Cn
n！
C1!C2!…C n!1 2 … n C1 C2 Cn
一般来说,Sn中任意一个置换 P分解成若干不相交的循环乘积,
P=(a1a2…ak 1) (b1b2…bk 2)… (c1c2…ck m)
其中 k1+k2+…+k m=n
这里 k循环出现的次数为 ck,用 (k)ck表示,
例如,(1)(23)(4567)属于格 (1)1(2)1(3)0(4)1(5)0(6)0(7)0
而 (1)(23)(45)(67)属于格 (1)1(2)3(3)0(4)0(5)0(6)0(7)0
4.4 Burnside引理
证 (1) (2) …( n) 即C1 C2 Cn
(·)…(·)(··)…(··)… (·…·)…(·…·)
_∧ _
/ \
1个
_∧ _
/ \
2个
____∧ ____
/ \
n个
\______ ______/
\/ C
1个
\________ ________/
\/ C
2个
\________ ________/
\/ C
n个一个长度为 k的循环有 k种表示,Ck个长度为 k的循环有 Ck!k 种表示,1,2,…,n的全排列共有 n!个，给定一个排列，装入格式得一置换，除以前面的重复度得
n!/(C1!C2!…C n!1 2 … n ) 个不同的置换,
Ck
C1 C2 Cn
4.4 Burnside引理
例 1 S4中 (2) 共轭类有 4!/(2!2 )=3
(1) (3) 共轭类有 4!/(C1!C3!1 3 )=8
(1) (2) 共轭类有 4!/(C1!C2!1 2 )=6
(2)k不动置换类设 G是 [1,n]上的一个置换群。 G≤Sn,
K∈ [1,n]G中使 k保持不变的置换全体，
称为 k不动置换类，记做 Zk.
2
C1 C3
C1 C2
1 1
2 1
2
4.4 Burnside引理
定理 置换群 G的 k不动置换类 Zk是 G的一个子群。
封闭性,k→k→k,k k.
结合性：自然。
有单位元,G的单位元属于 Zk.
有逆元,P∈ Zk,k→k,则 k→k,P ∈ Zk.
∴ Zk≤G.
P1 P2 P1P2
P P-1
4.4 Burnside引理
(3)等价类 举一个例子。
G={(1)(2)(3)(4),(12),(34),(12)(34)}.在 G下，
1变 2,3变 4，但 1不变 3。 Z1=Z2={e,(34)},
Z3=Z4={e,(12)}.对于 A4,
Z1={e,(234),(243)},Z2={e,(134),(143)}
Z3={e,(124),(142)},Z4={e,(123),(132)}
一般 [1,n]上 G将 [1,n]分成若干等价类，满足等价类的 3个条件,(a)自反性 ;(b)对称性 ;(c)传递性。
4.4 Burnside引理
一个由 G定义的关系 k：
若存在 p∈ G,使得 k→j 则称 kRj.显然 kRk；
kRj则 jRk； kRj,jRl则 kRl。 R是 [1,n]上的一个等价关系。将 [1,n]划分成若干等价类。
含目标集元素 k的在 G作用下的等价类也称为含 k的轨道。
p
4.4 Burnside引理
定理 设 G是 [1,n]上的一个置换群,Ek是 [1,n]在 G
的作用下包含 k的等价类,Zk是 k不动置换类。
有 |Ek||Zk|=|G|,
证 设 |Ek|=l,Ek={a1(=k),a2,…,a l} k=a1→a i,i=1,2,…,l,
P={p1,p2,…,p l}令 Gi=ZkPi,i=1,2,…,l.
Gi包含于 G(G关于 Zk的陪集分解 )i≠j,Gi∩Gj=Φ,
G1+G2+…+G l包含于 G,另一方面，任意 P∈ G,
k→a j→k PPj ∈ Zk,P∈ ZkPj=Gj.
∴ G包含于 G1+…+G l.从而,G=G1+G2+…+G l.
|G|=|G1|+|G2|+…+|G l|=|Zk|·l= |Zk|·|Ek|
Pi
· · ·
· ·
-1Pj-1P
4.4 Burnside引理
(4)Burnside引理设 G={a1,a2,…a g}是目标集 [1,n]上的置换群。每个置换都写成不相交循环的乘积。
G将 [1,n]换分成 l个等价类。 c1ak是在置换
ak的作用下不动点的个数，也就是长度为
1的循环的个数。
Burnside引理
l=[c1(a1)+c1(a2)+…+c 1(ag)]/|G|
4.4 Burnside引理
例如,G={e,(12),(34),(12)(34)},
c1(a1)=4,c1(a2)=2,c1(a3)=2,c1(a4)=0.
l=[4+2+2+0]/4=2,以本例列表分析：
1 2 3 4 c1(aj)
(1)(2)(3)(4) 1 1 1 1 4 (1)
(12)(3)(4) 0 0 1 1 2 (1) (2)
(1)(2)(34) 1 1 0 0 2 (1) (2)
(12)(34) 0 0 0 0 0 (2)
|Zk| → 2 2 2 2 8
Sjk k
aj
4
2 1
2 1
2
4.4 Burnside引理
Sjk=
对第 j行求和得 c1(aj),对第 k列求和得 |Zk|
表中元素的总和 =∑∑Sjk=∑|Zk|=∑c1(aj).
一般而言，与上表相仿，有下页表格，
其中 Sjk=
1,k =k,
0,k ≠k.
aj
aj
g
j=1
g
j=1
n
k=1
n
k=1
1,k =k,
0,k ≠k.
aj
aj
4.4 Burnside引理
Sjk k
aj 1 2 … n c1(aj)
a1 S11 S12 … S 1n c1(a1)
a2 S21 S22 … S 2n c1(a2)
… … … …
ag Sg1 Sg2 … Sg n c1(ag)
|Zk| |Z1||Z2| … |Z1| ∑|Zk|=∑c1(aj).g
j=1
n
k=1
∵ ∑Sjk=c1(aj),∑Sjk=|Zk|,设在 G作用下，
[1,n]分成 l个等价类。 [1,n]=E1+E2+…+E l.
g
j=1
n
k=1
4.4 Burnside引理
若 j,I同属一个等价类，则 Ei=Ej,|Ei|=|Ej|
因 |Ei||Zi|=|G|,故 |Zi|=|Zj|,∑|Zi|=|Ej||Zj|
∴ ∑|Zk|=∑∑|Zk|=∑|Ei||Zi|=∑|G|=l|G|
∴ l= ∑|Zk|= ∑c1(aj).
i∈ Ej
g
j=1
n
k=1
n
k=1
1
|G|
1
|G|
l
i=1
l
i=1
l
i=1i∈ Ej
4.4 Burnside引理
例 2 一正方形分成 4格,2着色，有多少种方案？图象：看上去不同的图形。方案：
经过转动相同的图象算同一方案。图象数总是大于方案数。
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
4.4 Burnside引理
不动,p1=(1)(2)…(16)
逆时针转 90,p2=(1)(2)(3 4 5 6)(7 8 9 10)
(11 12)(13 14 15 16)
顺时针转 90,p3=(1)(2)(6 5 4 3)(10 9 8 7)
(11 12)(16 15 14 13)
转 180,p4=(1)(2)(3 5)(4 6)(7 9)(8 10)
(11 12) (13 15)(14 16)
(16+2+2+4)/4=6(种方案 )
。
。
。
4.5 Pólya定理
设 Ω=[1,n],M={S1,S2,…S m}是 m种颜色的集合，对 Ω中的元素用 M中的颜色着色，
得到的图象集合用 M 表示,|M |=m,每个中的元素都有 m种着色可能,n个元的着色有 m 种可能。即共有 m 个图象。
设 G是以 Ω为目标记得置换群，是某一转动群 R的表示。 G是以 M 为目标记得置换群，是同一转动群 R的表示。
Ω Ω
Ω
n n
n
4.5 Pólya定理
G≌ R,G≌ R,G≌ G
一个着色图象在 G的作用下变为另一个图象，则这两个图象属于同一方案。
Pólya定理 设 G={P1,P2,…,P g}是 Ω上的一个置换群,C(Pk)是置换 Pk的循环的个数，
用 M中的颜色对 Ω中的元着色，着色方案数为 l=—[m +m +…+m ].C(P1) C(P2) C(Pg)1 |G|
4.5 Pólya定理
f:Ω→M,G 是作用在图象集合 M 上的置换群。对于 P∈ G,P=,k=1,2,…,n
T,P→P,P=,i=1,2,…,m,
T:G→G f i(k)=fi(k ),i=1,2,…,m,k=1,…,n,
P称为由 P诱导出的 M 上的置换。
G={P1,…,P g},G={P1,P2,…,P g}
T是 G到 G的同构映射。 C1(Pi)=m
Ω
k
kp
fi
fi
p n
△
_p
n
Ω
C(Pi)
4.5 Pólya定理
在 Pi作用下 M 中的不动图象的个数
C1(Pi)=m,C(Pi)表示 Pi的循环的个数，
即同一循环中的元素都着同一种颜色的图象在 Pi的作用下保持不变。
对应于 P∈ G,有 P∈ G,P是 M (图象集 )上的一个置换。现在要计算的也就是图象集在 G作用下的等价类的个数。下面对前例进行分析，然后推导到一般。
Ω
C(Pi)
Ω
4.5 Pólya定理
P1=(1)(2)(3)(4),P1=(1)(2)…(16)
P2=(4321),P2=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)
P3=(1234),P3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)
P4=(13)(24),P4=(1)(2)(35)(46)(79)(8 10)(11)(12)(13 15)(14 16)
C(P1)=4,C1(P1)=16=2
C(P2)=1,C1(P2)=2=2
C(P3)=1,C1(P3)=2=2
C(P4)=2,C1(P4)=4=2
求着色的方案数也即求图象的等价类个数。按
Burside定理，求等价类的个数归结为每个置换下的不动点 (不动图象 )的个数。
C(P1)
C(P2)
C(P3)
C(P4)
2 1
3 4
4.5 Pólya定理
证 对 Ω的 n个目标用 m种颜色着色的图象集为 M |M |=|M| =m
G的每一个元 Pi是 Ω上的一个置换，也对应了 M 上的一个置换 Pi,这样 G≌ G,T:Pi←→ Pi
在 Pi的作用下不动图象的个数 C1(Pi)等于 Pi
的同一循环中的目标都着相同色的选择的个数。即 C1(Pi)=m 。 因而在 G的作用下，
M (图象 )的等价类的个数。
l=—[C1(P1)+…+C 1(Pg)]=—[m +m +…+m ],
Ω |Ω| Ω
Ω
n
C(Pi)
Ω
C(P1) C(P2) C(Pg)1
|G|
1
|G|
4.6 举例
例 1 等边三角形的 3个顶点用红，兰，绿 3
着色，有多少种方案？
解 在 3维空间考虑,3顶点的置换群 S3.
(3),2个；
(1) (2),3个；
(1),1个；
l = (2·3 +3·3 +3 )/6=10
1
3
1 1
1 2 3
4.6 举例
例 2 甲烷 CH4的 4个键任意用 H,Cl,CH3,
C2H5 连接，有多少种方案？
解 CH4的结构是一个正 4面体,C原子居于正 4面体的中心。正 4面体的转动群按转动轴分类,顶点 -对面的中心,(1)(3) 8个；
棱中 -棱中,(2) 3个； 不动,(1) 1个；
6条棱,每条棱看作一有向边，正向重合与反向重合共 6·2=12个位置，故转动群的群元有 12个。 l=[11·4 +4 ]/12=[44+64]/3=36。2 4
4.6 举例
例 3 3个输入端一个输出端的布尔电路有多少种实质上不同的结构？
解 3个变量的布尔函数形式上有 2 =256个,但有的只是输入端的顺序不同,输入端的变换群是 S3。
输入端的电平取值共有 000~111计 8种。 输出
f,S3→H S3≌ H
Pj→h j= i=0~7
P1=(1)(2)(3),h1=
(1) (1) 1个 ;(3) (1) (3) 2个 ;(1) (2) (1) (2) 3个 ;
结构总数为 [2 +2·2 +3·2 ]/6=80
a1 a2 a3
a1 a2 a3
(i) (i) (i)
(i) (i) (i)
pj pj pj
000 001 010 011 100 101 110 111
000 001 010 011 100 101 110 111
3 8 1 2 2 1 1 4 2
4.6 举例
例 4 正 6面体的 6个面分别用红，蓝两种颜色着色，有多少方案？
正 6面体的转动群用面的置换表示：
面心 -面心 ± 90 (1) (4) 6个
180 (1) (2) 3个 顶点 -顶点
± 120 (3) 8个 棱中 -棱中
180 (2) 6个不动
(1) 1个 [12·2 +3·2 +8·2 +2 ]/24=10
。
。
。
。
2
2 2
2
3
6
3 4 2 6
4.6 举例
例 5 用 2种颜色给正 6面体的 8个顶点着色，
有多少方案？
解 用顶点的置换表示：
面心 -面心 ± 90 (4) 6个
180 (2) 3个 顶点 -顶点
± 120 (1) (3) 8个 棱中 -棱中
180 (2) 6个不动
(1) 1个 [17·2 +6·2
+2 ]/24=[34+3+32]/3=23
。
。
。
。
2
4
2 2
4
8
4 2 8
4.6 举例
例 6 在正 6面体的每个面上任意做一条对角线，
有多少方案？
解 在每个面上做一条对角线的方式有 2种，可参考面的 2着色问题。但面心 -面心的转动轴转
± 90 时，无不动图象。除此之外，都可比照面的 2着色。所求方案数：
不动 (1) 1个 2
面心 -面心 ± 90 (1) (4) 6个 无不动图象 0
180 (1) (2) 3个 3·2
顶点 -顶点 ± 120 (3) 8个 8·2
棱中 -棱中 180 (2) 6个 6·2
[2 +0+ 3·2 +8·2 +6·2 ]/24=[8+6+4+6]/3=8
。
。
。
。
6
2
2 2
2
3
6 4 2 3
6
4
2
3
4.6 举例
例 7 骰子的 6个面分别有 1,…,6 点，有多少种不同的方案？
解 1) 6!个图象的目标集,只有单位元有 6!
个不动点 (图象 )其他 23个群元不动点。由
Burnside引理有 [C1(e)]/24=6!/24=30个方案。 C1(p1)=C1(p2)=…=C 1(p23)=0
2) 2点,3点,6点各有两种取向，
1点,4点,5点各有一种取向，
故应有 30·2=240种方案。
· ·· ·· ··· ······ ··· ···
· ···· · ·· ·
4.6 举例
为了解决正多面体及一些对称对面体的计算问题介绍下面的定理。
定义 凸多面体与一个顶点相关的面角之和与 360 的差称为该顶点的欠角。
定理 凸多面体各顶点欠角的和为 720 (用欧拉定理证 )
。
。
4.6 举例
用正 5边形搭成的正多面体,
(5-2)·180/5=108,360 -3·108 =36。
720 /36 =20(个顶点 )
一个顶点 3条棱，重复度为 2,20·3/2=30条棱一个顶点相关 3个面,重复度为 5,20·3/5=12个面
用正 3角形搭成的面最多的正多面体,
360 -5·60 =60 。 720 /60 =12(个顶点 )
一个顶点关联 5条棱,重复度为 2,12·5/2=30条棱。
一个顶点关联 5个面,重复度为 3,12·5/3=20个面
。 。 。 。
。 。
。 。 。 。 。
4.6 举例
足球：
欠角 =360 –(108 +2·120 )=12
720 /12 =60(个顶点 ) 60·3/2=90(条棱 )
60/5=12(个 5边形 ) 60·2/6=20(个 6边形 )
(正 20面体砍去 12个顶点 )
。 。 。 。
4.7 母函数型式的 Pólya定理
l=—[∑m ] 目标集 [1,n]
m种颜色,b1,b2,…,b m m 用
(b1+b2+…+b m) (b1+b2+…+b m) …
(b1+b2+…+b m) 代替。 P(b1,b2,…,b m)
以 b1,b2,…,b m为复元的 n次对称多项式。
令 Sk=(b1+b2+…+b m)
m ~ S1 S2 …S n
P(b1,b2,…,b m)=—∑∏Sj
∑kCk(pi)=n
1
|G|
g
C(Pi)
i=1
C(Pi) C1(Pi) C2(Pi)2 2 2
n n n C(Pi)
k k k
C(Pi) C1(Pi) C2(Pi) Cn(Pi)
Cj(Pi)1
|G|
g n
i=1 j=1
4.7 母函数型式的 Pólya定理
例 1 有 3种不同颜色的珠子，串成 4颗珠子的项链，有哪些方案？
解 正 4边形的运动群绕心转 ± 90 (4) 2个
180 (2) 1个 绕轴翻转
(2) 2个
(1) (2) 2个 不动
(1) 1个
。
。
1
2
2
2
4
4.7 母函数型式的 Pólya定理
P(b,g,r)=[(b+g+r) +2(b +g +r ) +3(b +g +r )
+2(b+g+r) (b +g +r )]/8
=b +g +r +b g+b r+bg +br +g r+gr
+2b g +2b r +2g r +2b gr+2bg r+2bgr
例 2 4颗红色珠子嵌在正 6面体的 4个顶点上，有多少方案？
解 相当于对顶点 2着色。无珠设 b,
(1) 1个 ; (4) 6个 ; (2) 9个 ; (1) (3) 8个 ;
p=[(b+r) +6(b +r ) +9(b +r ) +8(b+r) (b +r ) ]/24
4 4 4 4 2 2 2 2
2 2 2 2
4 4 4 3 3 3 3 3 3
2 2 2 2 2 2 2 2 2
8 4 4 2 2 2 4 2 3 3 2
4.7 母函数型式的 Pólya定理
b r 的系数,—[——+6·2+9·——+8·2]=71 8!24 4!4! 4!2!2!4 4
4.8 图的计数
例 1 4个顶点的图，对完全图的边的 2着色
S4的每个置换对应 6条边的集上的一个置换
(1) (1) 1个
(4) (2) (4) 6个
(2) (1) (2) 3个
(1) (2) (1) (2) 6个
(1) (3) (3) 8个
P(x,y) = —[(x+y) +9(x+y) (x +y ) +8(x +y )
+6(x+y) (x +y ) ]
1
24
6 2 2 2 2 3 3 2
2 2 2 2
4
1
2
2
6
1
2 2
2 2
2
4.8 图的计数
=x +x y+2x y +3x y +2x y +xy +y6 5 4 2 3 3 2 4 5 6
4.8 图的计数
例 2 求 4个顶点的不同构的有向图的个数。
解 顶点置换 有向边置换
(1) (1) 1个
(1) (2) (1) (2) 6个
(2) (2) 3个
(1) (3) (3) 8个
(4) (4) 6个
P(x,y) = —[(x+y) +6(x+y) (x +y ) +3(x +y )
+8(x +y ) +6(x +y ) ]
4
2
2
12
2 5
6
4
3
12 2 2 2 5 2 2 6
3 3 4 4 4 3
1
24
4.8 图的计数
x y 的系数,—[——+6(1+—)+3—+0+0]=51 12! 5! 6!24 2!10! 4! 5!2 10
