组合数学课件：群

群6.1群（group）

6.2置换群

6.3群同态、群同构

6.4置换中的轮换

6.5Polya定理

6.6生成函数型的Polya定理6.1群(group)

定义1

代数系统（G，*）若满足以下条件：

(1)结合律：对a,b,c∈G，(a*b)*c=a*(b*c)；

(2)幺元：e∈G，使对a∈G，e*a=a*e=a；

(3)逆元：对G中幺元e及a∈G，a-1∈G使a-1*a=a*a-1=e，则称（G，*）为群。为醒目起见，群中特异元素e及求逆也常特别写出，如（G，*）又可记为（G，*，e)。(G，

*）之称谓代数系统是指对a,b∈G，有a*b∈G，即G中元素在运算“*”作用下保持封闭性。显见正整数连同其上的加法运算构成一代数系统,正整数在减法运算下不构成代数系统。又若仅有(1)成立时，称代数系统（G，*）为半群（semigroup）；若有(2)，(3)同时成立，称（G，*）为单子（monoid），或称幺半群、独异点。此外，因结合律能保证左逆元就是右逆元，右逆元就是左逆元，故条件(3)常改为对a∈G，a有左逆或a有右逆。当G为有限集时，称（G，*）为有限群；若G为无限集，则称（G，*）为无限群。有限群中G的基数|G|常称为群的阶数。

定义2

设（G，*）为群，若对a*b∈G，a*b=b*a成立，则称（G，*）为abel群。

例1

设Z为整数集，+、-、×、/分别为一般的加、减、乘、除法运算，则（Z

，+）为群，且因交换律成立，（Z

，+）又是abel群。（Z

，-），Z

，×），（Z

，/）均不成其为群，原因是：减法运算不能保持Z中元素的结合律。对乘法运算，特异元素0∈Z（称为零元）不存在逆元；而对除法，连封闭性都不能保证。故（Z

，-）仅为代数系统，（Z

，×）可为单子，（Z

，/）连代数系统都不是。

例2设（

Q+，×）为正有理数集及定义在其上的乘法运算所成之二元组，则（Q+

，*）为abel群。

例3设X为任意集合，P（x）表示X上的全部双射函数，“”为P（x）中元素的合成运算，幺函数IX（x∈X，IX（x）=x）为P（x）中的幺元，则（P（x），。，

IX）为群。一般来说（P（x），。，

IX

）不具交换性。

例4设Nk={0，1，…，k-1},+k,×k分别为定义在Nk上的模k加法及模k乘法运算，即对i,j∈Nk

，有i+kj≡(i+j)modk;i×kj≡(i×j)modk则(Nk

，+k)为群，(Nk

，×k)不成其为群的原因是Nk中的乘法零元“0”无逆。顺便指出，基数大于1的代数系统若有零元，则必不为群。

命题1

设（G，*）为群，则对a,b∈G

(1)！x∈G，使a*x=b；

(2)！y∈G，使a*y=b。

证明只证(1)，至少有一个x满足(1)，显见a-1*b∈G能充当x。令x=a-1*b，则a*x=a*(a-1*b)=(a*a-1)*b=e*b=b

又设x∈G∧a*x=b，则x=e*x=(a-1*a)*x=a-1*(a*x)=a-1*b

类似可证(2)。

推论1设（G，*）为群，则对

a∈G，有

(1)a*x1=a*x2

x1=x2

（左消律）

(2)y1*a=y2*a

y1=y2

（右消律）其中x1，x2

，y1

，y2∈G。

证明只证(1)，令a*x1=a*x2=b，则由命题1，满足a*x=b的x是惟一的，立得x1=x2

。同理可证(2)。

推论2群中惟有幺元是幂等元素。证明幺元素幂等显然,又设x2=x为G中任一幂等元。则因x2=x*x=x=x*e,由命题1即得x=e。

推论3

群（G，*）的运算表中的每一行、每一列都是G中元素的一个置换。

证明（1）设G={a1,a2,…},对a∈G，记运算表中对应于a所在的行为Ga={aa1,aa2,…,aai,…,aaj,…}则ai≠aj

a*aj≠a*aj（a*ai=a*aj

ai=aj的逆反命题）。由a的任意性知，G的运算表中每一行不会两次出现同一元素。（2）对ak∈G，有ak=a*(a-1*ak)∈Ga，即G中任一元素都出现在Ga中。于是，由（1）及（2）知G的运算表中每一行都是G中元素的一个置换。以上证法对列亦然。

定义3设（G，*）为群，A={a1,a2,…}

G，若 ∧对a∈A，G不能利用A\{a}的元素之乘幂完全表出，则称A为G的生成集。特别地，当A为单元素集{a}时，称a为G的生成元，并称G可由a生成。

定义4

设（G，*）为群，g∈G为G的生成元，则称（G，*）为循环群。

命题2任一循环群都是Abel群。证明留作练习题。

命题3设（G，*）是由g生成的有限循环群，如果|G|=n，则

(1)gn=e;

(2)G={g,g2,…,gn=e};

(3)不存在m(0<m<n)使gm=e。

证明先证（3），假定m∈Z+∧m<n能使gm=e，则对gk∈G，k=mg+r(0≤r<m)。于是，gk=gmq+r=(gm)q*gr=gr，这意味着G中任一元素都可写成gr的形式，注意到r<m，故G中至多有m个不同元素，这与|G|=n矛盾。所以使gm=e∧0<m<n的m不存在。

再证（2），{g,g2,…,gn}中元素互不相同。如若不然，有gi=gj，不妨设i<j≤n，于是gj-i=e，但j-i<n，而这是不可能的。注意到（G，*）是群，其中必有幺元，由（3）得gn=e（此即（1）），进而有G={g,g2,…,gn=e}

例5(Z，+)为无限循环群，其中1或-1都是生成元。例4的（Nk，+k)为k阶循环群。

定义5

设（G，*）为群，非空S

G且满足如下条件：

(1）对a,b∈S,有a*b∈S；

(2)对a∈S,有a-1∈S；

(3)（G，*）的幺元e∈S则称（S，*）是（G，*）的子群。子群也是群，因结合律具有遗传性，再加（1），2），（3）即知。

事实上，条件（3）可由（1）及（2）推得，故可取掉。特别地，当G为有限集时，上述定义中只要（1）满足即可。为此，再给出以下子群的定义：

定义6

设（G，*）为有限群，非空S

G，若对a,b∈S，有a*b∈S，则称（S，*）为（G，*）的子群。

定义7设（G，*）为群，非空SG，若对a,b∈S，有a*b∈S，且对a∈S，有a-1∈S，则称（S，*）为（G，*）的子群。

命题4定义6、定义7均符合定义5。

证明先证定义6符合定义5。任取a∈S，构造序列a,a2,a3,…,a|G|+1，因|G|有限，故序列中必有相同元素，令as=at，不妨设s<t≤|G|+1。因为e=a0=as-s=as*a-s=at*a-s=at-s

注意到t-s≤|G|及(S,*)的封闭性，令k=t-s，即有ak=e∈S，进而因ak-1∈Sak*a-1=e*a-1=a-1∈S,故定义6符合定义5。再证定义7也符合定义5。因a,b∈S

a*b∈S,a∈S

a-1∈S，故a∈S

a*a-1=e∈S，即见定义7符合定义5。

例6(N4，+4)的子群有({0},+4),({0,2},+4)及(N4，+4)本身。

例7

设Z为整数集，E为偶数集，则（E，+）为（

Z，+）的子群。6.2置换群

定义1

不失一般性，集合X=(1,2,…,n)到自身的一个双射函数φ:X→X称为一个n次置换，记作设f,g为两个n次置换

f和g间的运算“。”定义为f。g(t)=f（g（t））。其结果仍然是一个n次置换。f。g=由定义1可见，置换在运算“。”的作用下保持封闭。

命题1

设Sn为X上的全部置换所成之集（|Sn|=n!），则代数系统(Sn,。)构成群，此群常称为n次n阶的对称群。

证明结合律：对f,g,h∈Sn,有f。(g。

h)=(f。g)。h

这样，(f。g)。h可以无混淆的记成f。g。h。幺元：存在幺置换e∈Sn，e(x)=x使对f∈Sn，有f。e=e。

f=f

逆元：对f∈Sn，互换f的两个行得一置换f-1，显见f

f-1=f-1。f=e

f－１即为f的逆元。

定义2

若G

Sn∧(G,。)构成群，则称(G,。)为置换群。对称群是置换群的一个特例。置换群一般不具交换性。

例1(二面体群)

考虑正n边形（各顶点依次标以1，2，…，n）上的两类运算，一类是绕重心O（逆时针）旋转2k

π

/n弧度（k=0,1,…,n-1），可产生n种不同的图案，对应于X的n个不同的置换。另一类是当n为奇数时绕各边的中垂线翻转180°，或当n为偶数时绕各对角线及各对边中垂线（共n条）翻转180°。从而无论n是奇数还是偶数，又可产生n种不同的图案，对应于X的n种不同的置换。不难发现，以上2n种置换在相继运动（旋转或翻转）下构成一置换群，这类群常称为2n阶的二面体群。

例2(四面体群)考虑正四面体（各顶点依次标以1，2，3，4），任选一顶点，不妨取4，以4与1，2，3面的顶垂线为轴，（逆时针）旋转2kπ/3弧度（k=0,1,2）可得3种不同的图案。由于四面体有4个顶点，故共可产生3×4=12种不同的图案，这些图案在以上动作（旋转）下构成的群称为四面体群。显见，四面体群的阶是12。类似的还有正六面体、正八面体、正十二面体及正20面体群。

例3(Klein四群)考察图6.2.1所示的长方形，记X=(e,a,b,c)

其中：

e：什么也不做；

a：绕横轴旋转180°；

b：绕纵轴旋转180°；

c：绕原点平旋180°。图6.2.1例3图6.3群同态、群同构

定义1

设（G，*）和(H,。)是两个群，h∶G→H是G到H的映射。如果对a,b∈G有h(a*b)=h(a)。h(b)则称h为（G，*）到(H，。)的群同态。

命题1

设eG∈G,

eH∈H分别为群（G，*）及(H，。)的幺元，h∶G→H为群同态，则h(eG)=eH，h(a-1)=(h(a))-1

证明因h(eG)=h(eG*eG)=h(eG)。h(eG),又注意到群中惟幺元是幂等元，故

h(eG)=Eh又h(a)。h(a-1)=h(a*a-1)=h(eG)=h(a-1*a)=h(a-1)。h(a)=eH故h(a-1)=(h(a))-1

命题3

设（G，*）是群，(H，。)为一代数系统，若存在满映射h∶G→H，使对a,b∈G有h(a*b)=h(a)。h(b)则(H，。)必为群。命题3可以看作命题2的直接推论。根据h是单射、满射及双射，群同态分别称为单同态、满同态及同构。从群（G，

*）到自身的同态称为自同态，从群（G，*）到自身的同构称为自同构。

例1

在代数系统(N5，×5)中，记

N*5=N5\{0}。构造映射h：N4→N*5，有h(0)=1;h(1)=2;h(2)=4;h(3)=3对照二者的运算表，易见(N4,+4)同构于(N*5,×5)；又因(N4,+4)是群，故知(N*5,×5)也是群。

例2

任一k阶循环群（G，*）都同构于(Nk,+k)。事实上，因若a∈G是（G，*）的生成元，则G={a,a2,…,ak=e}，构造映射h:Nk→G,h(imodk)=ai由于

h(i+kj)≡h((i+j)modk)=a(i+j)=ai*aj=h(imodk)*h(jmodk)又显见h是Nk到G的双映射函数，所以（G，*）和(Nk,+k)同构。

命题4(Cayley定理，1854)

任一n阶群，都同构于一n次n阶置换群。

证明设（G，*）是一n阶有限群，由6.1节命题1的推论3可知，（G，*）的运算表中每一行,每一列都是G的一个置换。对应于元素a∈G的行置换是pa(x)=a*x,即对应于G的所有元素的行的置换为PG。下面证（PG,。)是一群（其中。为置换间的合成运算）。封闭性：对a,b∈G，有

pa。

pb(x)=a*(b*x)=(a*b)*x=pa*b(x)

幺元：设e是（G，*）的幺元，对a∈G，有pe。

pa=pa。

pe=pa即pe为（PG,。)的幺元。

逆元：对a∈G，设a-1∈G为a的逆元，则pa。p-1a=p-1a=pe。即对pa∈PG，存在逆p-1a∈PG

。结合律由置换的合成运算立得。故知（PG,。)为群。下证（G，*）与（PG,。)同构。构造h:G→Pa,h(a)=pa,显见h为双射函数,又因h(a*b)=pa*b=pa。pb=h(a)。h(b),即见h是同态。这就证明了h是同构，亦即（G，*）与（PG,。)同构。

定义2

设（H，*）是群（G，*）的子群，则称aH={a*h|h∈H},Ha={h*a|h∈H}分别为由元素a∈G所确定的子群（H，*）的左陪集,右陪集，a称为该左、右陪集的表示元。如下只讨论左陪集，所得结论对右陪集也平行成立。

命题5

设（H，*）是（G，*）的子群，aH,bH是二任意左陪集，则或者aH=bH，或者aH∩bH=。

证明假定aH∩bH≠，即f(f∈aH∧f∈bH)，于是h1,h2∈H，使f=a*h1=b*h2

a=b*h2*h-11。设x是aH中任一元素，即有h3∈H使x=a*h3

x=b*h2*h-11*h3，但h2*h-11*h3∈H,故x∈bH。反之，若x∈bH

x∈aH，即有aH=bH。又aH和bH均非空集，且aH=bH和aH∩bH=不可兼得，所以命题为真。

命题6

H的任意陪集的大小是相等的。

证明对a∈G，h1,h2∈H，若h1≠h2，则a*h1≠a*h2。所以aH中不会产生二相同元素，这推得|aH|=|H|，亦即H的任一陪集大小相同，且均与H相等。由于（H，*）是（G，*）的子群，幺元e∈（H，*），故对a∈G

a∈aH， 。由以上二命题即可断言H的全部左陪集构成G的一个划分，且该划分中的块均具有相同的基数。换言之，|G|=α|H|，其中a为H的左陪集的个数。于是有以下命题：

命题7(Lagrange定理）

有限群的任意子群的阶数可以整除群的阶数。推论1素数阶的群惟有两个平凡子群。推论2有限群的任一元素的阶必可整除该群的阶。推论3素数阶的群必为循环群。推论4任意四阶群或为循环群或为Klein四群。

定义3

设（H，。）是（G，。）的子群，对g∈G,若gH=Hg，则称（H，。）为（G，。）的正规子群。等价的说法是,对g∈G，有H=gHg-1。

命题8

设A

G,H

G，且（H，。）是群（G，。）的正规子群，则

换言之，（G，。）的正规子群与G的子集（相乘）可交换。

命题9(1）设（H，。）是（G，。）的子群，则H的全部左陪集{gH|g∈G}或右陪集{Hg|g∈G}构成G的划分。这个划分的类所成之集常记为G/H，称为G对于H的商集，且有

（2）如果（H，。）对（G，。）是正规的，则商集G/H对如下定义的乘法K*K′={x。x′|x∈K,x′∈K′;K,K′∈G/H}构成群。6.4置换中的轮换6.4.1轮换与对换

设X={1,2,…,n}，X上的任一置换f都联系着一个有向图G=(X,E)，其中i,j∈X,(i,j)∈E当且仅当f(i)=j。由于f是从X到自身的双射函数，故对

i∈X，其入度和出度都是1。考察序列k,f(k),f2(k),…

因X为有限集，故序列中必有重复出现的元素，不难证得最早重复出现者必为k。如若不然，设ft(k)是最早重复出现的元素，即有ft(k)=fs(k)(1≤t<s)，由最早性知ft-1(k)≠fs-1(k)。但这与f所具有的性质i≠j

f(i)≠f(j)相矛盾。设fm(k)=k是最早重复出现的元素，则称k,f(k),f2(k),…,fm(k)是一个轮换，记作(kf(k)f2(k)…fm-1(k))

m常称为该轮换的长度。长度为2的轮换又称为对换或换位。显见，由f决定的有向图G=(X,E)的每个连通分支是一个轮换，且f的所有不同的轮换形成集合X的一个划分。设则可产生四个轮换:(132)、(4)、(5)、(6)。置换常记为若干轮换的乘积形式，且如不记顺序，这种表示还是惟一的。例如,f可记为f=(132)(4)(5)(6)，或更简单的记作f=(132)。

上述记法对于直接计算若干置换的乘积是很方便的。设有如下置换：

f=(134)(26)

g=(152)(364)

h=(1456)

则

f。g。h=(134)(26）（152）（364）（1456）

先看数字1，从右向左依次考察各轮换，即可得出1所经历的变换1→4→3→3→3→4记下（14…）；再考察4所经历的变换4→5→5→2→6→6

记下（146…）；再考察6所经历的变换6→1→1→5→5→5

接下去是5→6→4→4→4→1因此，第一个轮换是（1465）；然后取出不在这个轮换中的最小整数（这里是2），用同样方法作出第二个轮换，即2→2→1→1→3

3→3→6→6→2→2因此f。g。h=(1465)(23)

结合以上过程不难给出一般情况下求置换的不交轮换乘积表示的算法。该算法反过来即为置换可表示为不交轮换之积的证明。对置换中的轮换(12),(34)及(5)，可分别独立解释为即不在各轮换中出现的元素保持不变。(12)，(34)及(5)之间的乘积关系可解释为轮换（即相应置换）间的合成运算。亦即

更进一步，还可把轮换分解成若干对换之积，但这种分解并不惟一，其一般分解可用归纳法证明，这里从略。如下仅给出一个例子：(4321)=(12)(13)(14)=(23)(24)(21)=(23)(24)(21)(13)(31)虽然轮换(4321)可有多个不同形式对换积的分解式，但在这些分解式中，对换因子个数的奇偶性却是不变的。如(4321)的各种对换乘积分解式中对换的数目均为奇数。任意置换的阶等于它的不相交轮换之长度的最小公倍数n。事实上，若设k,l,…,m的最小公倍数为n，且f=fk。fl。…。fm=(a1a2…ak)。(b1b2…bl)。…(c1c2…cm)

则fn=fnk。fnl。…。fnm=e。e。…。e=e

故知f的阶为n。

例1去掉大小王后，52张扑克牌加以编码1,2,…,52，则这副牌连续洗8次后又恢复到原来牌序。

解第一次洗牌可用置换表示为

P=(1)·(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)其中，有2个1-轮换，1个2-轮换，6个8-轮换，由于各轮换长度的最小公倍数(1,1,2,8,8,8,8,8,8)=8，故知扑克牌洗8次后又会恢复到原来的牌序。6.4.2置换的奇偶性及对换的性质设f=a1a2…an为集合S={1,2,…,n}上的一个置换，若对i<j，有ai>aj，则称aj出现了一个逆序(或称（ai,aj

）为一逆序)。aj的逆序（个）数记为invs

(aj)，显见invs(aj)为满足i<j∧ai>aj的i的个数。若用invs(f)记置换f的逆序数，则invs(f)∷=。例如：对f=45123有invs(1)=2，invs(2)=2，invs(3)=2，invs(4)=0，invs(5)=0因此 invs(f)=2+2+2+0+0=6

又对f=12345，由invs(f)=0，知幺置换的逆序数为0。

若记置换f的符号为sign(f)，则sign(f)∷=(-1)invs(f)

若sign(f)=-1，则称置换f为奇置换；若sign(f)=1，则称置换f为偶置换。幺置换为偶置换。一个置换的奇偶性很容易从置换的不交轮换乘积分解式而得。

性质1

若t=(ij)为一对换，则t2=e，且t=t-1。

性质2

任一对换t=(ij)为一奇置换。事实上，若设t=(ij)为S={1,2,…,n}的一个置换，即t=(ij)=(1,2,…,i-1,i,i+1,…,j-1,j,j+1,…,n)其中

invs(1)=invs(2)=…=invs(i-1)=invs

(j-1)=…=invs(n)=0

invs(i+1)=…=invs(j-1)=1共j-1-(i+1)+1=j-i-1个逆序）

invs(i)=j-1-i+1=j-i

（共j-i个逆序）从而invs(t)=j-i-1+j-i=2(j-i)-1，故知，对换t=(ij)为奇置换。性质3

对任一置换f及对换t=(i,i+1)，有invs(f)=invs(ft)±1例如且有invs(f)=invs(1)+invs(4)+invs(2)=1+1+4=6

invs(ft)=invs(1)+invs(2)=1+4=5

即invs(f)=invs(ft)+1

性质3反映了将t=(i,i+1)作用于f时，f的逆序数增（或减）1，而逆序数增（或减）1恰好改变了f的奇偶性。对任一置换f若用形如(i,i+1)的对换将序列a1a2…an变为12…n，即将f变为恒等或幺置换，问最少需要多少个这样的对换？例如即共用了6个形如(i,i+1)的对换。注意45123的逆序数为6。

一般情况下，可以证明下面若干结论：（１）将置换f的简记形式a1a2…an变为12…n所需的形如(i,i+1)的对换的最小个数等于f的逆序数invs(f)。证明分两步：首先,证明f=a1a2…an一定可以通过invs(f)个对换变为12…n。思路是通过逐个考察元素1,2,…,n-1的逆序数并重复对换相邻项,而将各元素换到自然位置，而这种操作是机械式的。其次，证明invs(f)是将f=a1a2…an变为12…n的最小次数，这是由于若将(i,i+1)施加于f得到f′时，有

invs(f)+1,若ai<ai+1

invs(f)-1,若ai>ai+1invs(f′)=

（２）若置换f经过q个形如(i,i+1)的对换，而将序列a1a2…an变为幺置换12…n，则q与invs(f)具有相同的奇偶性。注意到(1)中曾证明过一定能用invs(f)次操作使invs(f)降到0。又若用q次形如(i,i+1)的对换使得invs(f)变为0，必有q≥invs(f)。其中多余部分出现了使invs(f)加1的冗余操作及相同次数减1的冗余操作,去掉往返的偶数次冗余操作后，所剩操作次数一定是invs(f)次。故知q与invs(f)具有相同的奇偶性。

（３）对称群Sn的每个置换f均可表示为q个对换（不一定形如(i,i+1)）之积，且若各对换形为(i,i+1)时，q与invs(f)具有相同的奇偶性。注意到f=a1a2…an一定可以通过q个对换t1t2…tq变为12…n。即

即f可表示为q个形如(i,i+1)的对换之积。又若f可表示为q个形为(i,i+1)的对换之积(即f=tq·tq-1…t1)时，则可推知f·t1·t2…tq=e，由（2）知与invs(f)具有相同的奇偶性。

（4）对称群Sn是由(12),(23),…,(n-1,n)这n-1个对换生成的。（５）sign(f。

f′)=sign(f)sign(f′)。由（3）知Sn中的每个置换f均可分解为q个形如(i,i+1)的对换之积，而q又与invs(f)同奇偶,对f′亦有q′与invs(f′)同奇偶,故sign(f。f′)=(-1)q+q′=(-1)invs(f)+invs(f′)

=(-1)invs(f)·(-1)invs(f′)=sign(f)·sign(f′)

（６）若置换f可表示为q个对换之积，则q与invs(f)有相同的奇偶性。令f=t1。t2。…。tq

，其中ti(i=1,2,…,q)都是对换，且都是奇性的。由（５）知(-1)invs(f)=sign(f)=sign(t1)…sign(t2)sign(tq)=(-1)q

故invs(f)与q具有相同的奇偶性。(7)置换的奇偶性等于其偶数长轮换的个数的奇偶性。即设置换f分解的轮换积中偶数长轮换的个数为q，则f与q具有相同的奇偶性。首先，任一k阶轮换可分解为k-1个对换之积,即(a1a2…ak)=(a1a2)(a2a3)…(ak-1ak)其次，设f中有λ1个1-轮换，λ2个2-轮换，…,λk个λk-轮换，将其记为 ，这些轮换可分解的对换数为m=λ2+2λ3+3λ4+4λ5+…+(k-1)λk=λ2+λ4+…+2λ3+2λ4+…由（6）知，f与m同奇偶，即f与λ2+λ4+…同奇偶。从而，f与偶数长轮换的个数同奇偶。例如,(1234)(5),(123)(4567)都是奇置换，(12345),(1234)(567)(89)都是偶置换。

例2（15-谜题）图6.4.1给出了4×4棋盘上棋子的两种布局,棋子分别标以数字0,1,2,…,15。若规定只允许出现0棋子与其相邻的棋子对换，证明其中的置换（a）布局不能演变为（b）布局。证明从（a）变到（b）相当于做以下置换f：这是一个奇置换。图6.4.1例2图

另一方面，按移动规则将0从右下角换出，最后再返回到右下角，往返必须经过偶数次对换。亦即，按移动规则使０恢复原位一定会产生一个偶置换。由此推知，按照题给移动规则，不能将（a）布局变到（b）布局。因此，只有当给定布局间能用偶置换表示时，才能按移动规则将一种状态演变到另一种状态。

定义1

设（G，。）为一置换群，若g∈G，使得s=g。t。g-1，则称s和t在G中共轭。

命题1“共轭”是G上的一种等价关系。

证明自反性：s=e。s。e-1,e∈G。对称性：s=g。t。g-1

t=g-1。s。g=h。s。h-1,h=g-1∈G。传递性：s=g。t。g-1∧t=h。u。h-1

s=g。(h。u。h-1)。g-1=(g。h)。u。(g。h)-1,g。

h∈G。

命题2

两个置换s与t在n次对称群（Sn，。）中共轭，当且仅当它们的各种长度的轮换的数目相同。

证明必要性：令s=g。t。g-1，

g∈Sn定义为bpq=g(apq)，t=(a11a12…a1i)(a21a22…a2j)…(am1am2…amk

)于是s(bpq)=g。t。g-1(bpq)=g。t(apq)=g(apq+1)=bpq+1

因此s=(b11b12…b1i)(b21b22…b2j)…(bm1bm2…bmk)

充分性：如果s与t的各种长度的轮换的数目相同（不妨设s，t就为必要性证明中所示形式），则s=g。t。g-1

，即s和t在Sn中共轭。例3

S3有三个共轭类，分别对应于3的三个拆分：3=1+1+1,3=1+2,3=3第一类仅含一个置换：第二类含有三个置换：第三类含有二个置换：

定义2

设f为n次对称群（Sn，。）中的任一置换，若f可表示为λi(i=1,2,…,k)个长为i的轮换之积，则称f属于∏iλi型的置换。例如,f=（1）（23）（4567）属于11213041型的置换，或省去指标为0的项而简写为112141型。显见

命题3

（Cauchy定理）Sn中属于 型的置换的数目为证明具有上述要求的置换的格式为

格式中的n个*可用n！种方法代之以1，2，…，n，但是这样得出的置换并不都是相同的，因为λi个长为i的轮换可以互换而f不变。在这种意义下，同一f重复的次数为。另外，对每个长为i的轮换（有向圈）为首的数字有i种不同的写法。在这种意义下，同一f重复出现的次数是 。因此， 型的置换的个数是例如，当n=3时，1·2型置换的个数为参见前例，这三个置换分别是a,b,c。

推论在Sn中 型的共轭类的元素个数为h(λ1,λ2,…,λk)。定义3设（G，。）是作用在有限集X(|X|=n)上的置换群，若对x,y∈X,g∈G，使得y=g(x)，则称“相对于G，x等价于y”。记作x≡y(G)

显见“≡”是一种等价关系（其证明作为练习）。等价关系“≡”的等价类称为群（G，。）的轨道（Orbit）。若当（G，。）是由置换f生成的循环群，即G={e,f,f2,…}，则（G，。）的轨道就是f中的轮换。由此，轨道可看作轮换概念的推广。

定义4

对k∈X，定义Gk={g|g∈G∧g(k)=k}为使元素k保持不动的全部置换，常称Gk为k的不动置换类。注意到f,g∈Gkf。g(k)=f(k)=k

f。g∈Gk（封闭性），即得如下命题：

命题4(Gk，。）是（G，。)的子群。如下由建立Ok到G/Gk的一个双射函数来证明|G/Gk|=|Ok|。

命题5

设（Gk，。）是（G，。）的使k不动的子群，Ok是G的包含k的轨道，即Ok={y|k≡y(G)}={y|

g∈G,g(k)=y}

则 |Gk|·|Ok|=|G|

证明根据6.3节命题9，有

事实上，对y∈Ok，因至少g∈G使g(y)=k，就令y对应商集G/Gk中的类Gk。g。若g(y)=k∧h(y)=k，h,g∈G

h。g-1(k)=k

h。g-1∈Gk

h∈Gk。gGk。g=Gk。h即见这种对应构成Ok到G/Gk的单射。对于Gk。g∈G/Gk,Gk。g是g-1(k)∈Ok的像,又见这种对应构成Ok到G/Gk的满射。从而Ok与G/Gk间有一双射函数存在，故

|G/Gk|=|Ok|

例4

考虑由f=（123）（45）生成的群（G，。），其中G={f,f2,f3,f4,f5,f6=e},f2=(132)(4)(5),f3=(1)(2)(3)(45)f4=(123)(4)(5),f5=(132)(45),f6=(1)(2)(3)(4)(5)轨道为O1={1,2,3};O4={4,5}

（G，。）的使1不变的子群为(G1={f3,f6},。)即见|G1|×|O1|=3×2=6=|G|

命题6（Burnside引理）设λ(g)是在置换g作用下X中不动的元素的个数（即g的长为1的轮换的个数），则n次对称群（Sn，。）的子群（G，。）的轨道数为 ，其中LG为G的轨道集。

证明如下用两种不同的方法求算适合g(k)=k，g∈G，k∈X的序偶(g,k)的个数，即如果j与k属于同一轨道，则因此例5

对前边的例子，应用命题6有λ(f)=0,λ(f2)=2,λ(f3)=3,λ(f4)=2,λ(f5)=0,λ(f6)=5

例6

一个正方形均分成4个格子，用两种颜色对4个格子着色，若经旋转可以吻合的方案算作同一个方案，问能得到多少种不同方案的图像。

解每格有两种颜色可供选择，故所有可能的图像共有16种，记为X={X1,X2,…,X16}。当每个图像都绕中心轴逆时针旋转0°、90°、180°、270°时，都可得到X的一种排列，记4种排列为G={P0,P90,P180,P270}。若记为连续动作，Px,Py∈G，Px。Py为先作用Py后作用Px

，则（G，。）构成X上的一个置换群，从而问题归结为求置换群（G，。）的轨道（旋转等价类）数。

不难求得λ(P0)=16,λ(P90)=λ(P270)=2,λ(P180)=4，故（G，。）的不同轨道数为亦即在旋转吻合的前提下共有6种（不同等价类）图案。

例7

考察由蓝、白、黄三种颜色的珠子中选取5粒串成的手镯，如将一只手镯经（逆时针方向）旋转而得另一只手镯视为同一手镯，则称二手镯是旋转等价的。试求在旋转等价的意义下不同手镯的数目。

解设X是不考虑旋转等价时的手镯，则显见X={f:A→B}，其中A={1,2,3,4,5},B={蓝，白，黄}。|X|=|B||A|=3·3·3·3·3=35=243。将手镯的（逆时针）旋转方式定义为Pk(mod5)。令G={Pj|j≡k(mod5)∧k∈Z+},则（G，。）为X上的一个置换群。其中为连续动作，Px。Py为先作用Py后作用Px。

对任意手镯，若珠子颜色全同，则任意一种旋转都会使该手镯自身变到自身，即旋转不变。又当手镯中珠子粒数为素数时，则不会出现不同色的手镯保持不变的情形。本例中5为素数，即只有全白、全蓝及全黄这三种手镯是旋转不变的。故λ(P1)=λ(P2)=λ(P3)=λ(P4)=3。由Burnside定理，在旋转等价的意义下，不同手镯的数目应为

利用不同手镯数目的计算结果，可获得数论中Fermat（小）定理的一个有趣证明。

对素数p，考察由a种珠子中选取p粒串成的手镯，在旋转等价的意义下，不同手镯的数目为由于手镯的数目总是整数，从而p|a(ap-1+p-1)，即p或者整除a，或者整除ap-1-1+p。而对后者，可得p|(ap-1-1)。由本例即得Fermat（小）定理：对a,ap-a≡0(modp)（p为素数），或对a,ap≡a(modp)，或对a,ap-1≡1(modp)。6.5Polya定理

定义1

设X={1,2,…,n}为染色对象集，A={a1,a2,…,am}为颜色集，（G，。）为X上的一个置换群，函数φ:x→A为一种染色（方案），φ把对象i∈X染上颜色φ(i)∈A。注意：对g∈G,φg也是一种染色。例如若g∈G，使得φ1g=φ2，则称二染色φ1与φ2属于同一格式（或属同一类）,记作φ1~φ2。显见“~”是一种等价关系。定义2

设g∈G，令λi(g)表示g中长为i的轮换的个数，则多项式称为G的轮换指数。

命题1(Polya计数定理）根据定义1和定义2，相对于G的格式的数目为

证明记Φ={φ|φ:X→A}，对φ∈Φ,

g∈G,定义g:Φ→Φ,g(φ)=φgc断言g是Φ到自身的双射函数。因Φ为有限集，故只需证g为单射即可。事实上φ1≠φ2

φ1g≠φ2gg(φ1)≠g(φ2)。令S表Φ中元素的全部置换，则g∈S，因为即ψ:G→ψ(G)

S,ψ(g)=g∈S为一双射函数。因此，G=ψ(G)={g|g∈G}与G的基数相同。此外(G,。)构成(S,。)的子群。事实上，因若g,h∈G，则

若g∈G，使φ2=g(φ1)=φ1g，即φ1与φ2属于G的同一轨道，则φ1和φ2等价。因此，相对于G的格式的数目等于G的轨道数。由Burnside定理，G的轨道数为其中,v(g)是满足φg=φ的染色φ的个数，而φg=φ表示φ使g的每个轮换中的元素染上同样的颜色,因此v(g)等于g的轮换集合（该集的元素个数为 )到m种颜色的映射的个数。因此

例1

令X={1,2,3,4,5,6},A={b,w}。把X中的元素看作立方体的6个面：1表顶面；3表底面；2表迎面；4表背面；5和6表左、右侧面。A的元素看作黑白两种颜色。下面在旋转等价的意义下计算立方体染色的格式数。首先构造立方体的旋转群（G，。），并把一种染色看作X到A的一个映射。上、下底面不动，每次旋转（右转）一个面、二个面、三个面，可得X的3个置换：g1:(1)(3)(2645);g2:(1)(3)(24)(65);

g3:(1)(3)(2546)

前、后面不动，每次旋转（逆时针）一个面、二个面、三个面，可得X的3个置换：g4:(2)(4)(1536);g5:(2)(4)(13)(56);g6:(2)(4)(1635)

左、右侧面不动，仿上可得三个置换：g7:(1234)(5)(6);g８:(13)(24)(5)(6);g９:(1432)(5)(6)

分别绕四条对角线旋转120°、240°可得8个置换：g10：(145)（632）； g11：（152）（643）g12：（154）（623）；

g13：（125）（634）g14：（126）（345）；

g15：（162）（354）g16：（164）（352）；

g17：（146）（325）

此外分别以六对对角平行棱线的中点为轴线旋转180°，共可产生6个不同置换：g18：（15）（63）（24）；g19：（16）（35）（24）g20：（12）（43）（56）；g21：（14）（23）（56）g22：（25）（64）（13）；g23：（26）（54）（13）再加单位元（幺置换）g24：（1）（2）（3）（4）（5）（6），共有24个置换。在上述立方体的染色问题中，

G的轮换指数易见为从而由命题1，六面体每面可染两种颜色的格式数为P(G;2,2,2,2,2,2)=10

例2

类似于例1，对立方体的8个顶点着两种颜色的方案数，可由构造8个点上的置换群G并用命题1求算如下：

例3

骰子的六个面分别有1，2，3，4，5，6个点，试求旋转等价意义下，六个面的分布方案数。

解六个面用6种颜色着色，各面颜色互不相同，共有6！种方案。又依例1，六面体旋转运动群共有24个置换。分别将各置换同时作用于6！种方案，则除幺置换能使各方案保持不动外，其余23种置换的任一种都不能使6！种方案的任一方案置换不变。故除幺置换的所有置换的置换不变元的个数都是0，而幺置换的置换不变元是6！。由Burnside定理，不同的方案数为

例4

等边三角形V1V2V3，若以红，白，蓝三色涂染各顶点，试求置换等价意义下的染色方案数。

解构造三角形的旋转置换群（G，。）。分别绕形心旋转（逆旋）120°、240°可得二置换：g1:(V1V2V3);g2:(V3V2V1)

分别绕三边中垂线翻转180°可得三个置换：g3:(V1)(V2V3);g4:(V1V3)(V2);g5:(V1V2)(V3)

不作任何动作可得到置换（幺元）g6:(V1)(V2)(V3)

故不同方案数为

例5

对正四面体的4个顶点用4种颜色着色，求置换等价意义下的不同方案数。

解使正四面体V1V2V3V4重合的刚体运动有两类，一类是绕各面的中垂线分别旋转0°、120°和240°；一类是绕过二对边中点的连线旋转180°，从而可得群G的各置换如下：(V1)(V2)(V3)(V4) (V1)(V2V3V4) (V1)(V4V3V2)(V2)(V1V3V4) (V2)(V4V3V1) (V3)(V1V2V4)

(V3)(V4V2V1) (V4)(V1V2V3) (V4)(V3V2V1)

(V1V2)(V3V4) (V1V3)(V2V4) (V1V4)(V2

V3)故不同的方案数为

例6（分放问题）将4个球a，a，b，b放进两个有编号的盒子A，B中，试问有几种放法？

解令X={a1,a2,a3,a4}，其中,a1=a2=a,a3=a4=b。因对任一放法,对调a1与a2或a3与a4仍属同一放法，故相应的置换群(G,。)的各置换如下：g1:(12)(3)(4); g2:(1)(2)(34)

g3:(12)(34); g4:(1)(2)(3)(4)从而各分放方案为￠|aabb,a|abb,b|aab,aa|bb,ab|ab,aabb|￠,abb|a,aab|b,bb|aa

命题2(Polya定理)

n个物件中恰有αi个物件染成ai色（i=1,2,…,m）的格式数为