組合數(shù)學(xué)（第二版）波利亞(Pólya)定理

波利亞(Pólya)定理6.1群論基礎(chǔ)6.2置換群6.3伯恩賽德(Burnside)引理6.4Pólya定理6.5母函數(shù)型的Pólya定理6.6應(yīng)用

6.1群論基礎(chǔ)

6.1.1群的概念

定義6.1.1給定非空集合G

及定義在G上的二元運(yùn)算“·”,若滿足以下四個(gè)條件,則稱集合G

在運(yùn)算“·”下構(gòu)成一個(gè)群,簡(jiǎn)稱G

為一個(gè)群:

(1)封閉性:a,b∈G,則a·b∈G;

(2)結(jié)合律:(a·b)·c=a·(b·c);

(3)單位元:存在e∈G,對(duì)任意a∈G,有a·e=e·a=a;

(4)逆元素:對(duì)任意a∈G,存在b∈G,使得a·b=b·a=e,稱b為a的逆元素,記為a-1.)

群的運(yùn)算符“·”可略去,即a·b=ab.

群的運(yùn)算并不要求滿足交換律.如果某個(gè)群G中的代數(shù)運(yùn)算滿足交換律,則稱G為交換群或Abel群.

群的元素可以是有限個(gè),叫做有限群;也可以是無限個(gè),叫做無限群.以|G|表示有限群中元素的個(gè)數(shù),稱為群的階,那么當(dāng)G為無限群時(shí),可以認(rèn)為|G|=∞.

【例6.1.1】偶數(shù)集,整數(shù)集Z,有理數(shù)集Q,實(shí)數(shù)集R,復(fù)數(shù)集C關(guān)于數(shù)的加法構(gòu)成群,稱為加法群.

因?yàn)閿?shù)的運(yùn)算對(duì)加法滿足定義6.1.1的要求(1)和(2).其中的單位元為0,每個(gè)數(shù)a關(guān)于加法的逆元為:a-1=-a.

但是,關(guān)于數(shù)的乘法,這些集都不構(gòu)成群.因?yàn)樵谂紨?shù)集中關(guān)于普通乘法不存在單位元.而在Z、Q、R、C中,雖然關(guān)于普通乘法有單位元1,但數(shù)0沒有逆元.

6.1.2群的性質(zhì)

定理6.1.1群具有以下性質(zhì):

(1)單位元e唯一;

(2)逆元唯一;

(3)滿足消去律:即對(duì)a,b,c∈G,若ab=ac,則b=c;若ba=ca,則仍有b=c;

(4)a,b∈G,則(ab)-1=b-1a-1,更一般有(ab…c)-1=c-1…b-1a-1;

(5)若G是有限群,則對(duì)任意a∈G,必存在一個(gè)最小常數(shù)r,使ar=e,從而a-1=ar-1.r稱為元素a的階.

證性質(zhì)(1)~(4)顯然.只證明性質(zhì)(5).

設(shè)|G|=n,由G的定義知:

由抽屜原理知,必存在整數(shù)m,k,滿足1≤m<k≤n+1,使得am=ak

,即ak-m

=e,令r=k-m,則ar=e,即a.ar-1=e,所以a-1=ar-1.

6.1.3子群

定義6.1.2設(shè)G是群,H是G的子集,若H在G的原有運(yùn)算下也構(gòu)成一個(gè)群,則稱H是G的子群.

【例6.1.9】任何群G至少有兩個(gè)子群:

H1=G,H2={e|e∈G為單位元}.

【例6.1.10】對(duì)于乘法運(yùn)算,H={1,-1}是G={1,-1,i,-i}的子群.

【例6.1.11】偶數(shù)加法群是整數(shù)Z的子群,Z是有理數(shù)加法群Q的子群,Q又是實(shí)數(shù)加法群R的子群,R是復(fù)數(shù)加法群C的子群;對(duì)乘法群而言,也有Q1

是R1的子群,R1

是C1的子群.

【例6.1.12】任選群G的一個(gè)元素a,設(shè)a的階為r,則H={a,a2,…,ar-1,ar=e}是G的子群.這樣的群H是由某個(gè)固定元素a的乘方組成的,稱為循環(huán)群,或稱H是由元素a生成的群,a叫做H的生成元.

定理6.1.2有限群的階數(shù)必能被其子群的階數(shù)整除.

6.2置換群

定義6.2.1有限集合S到自身的一個(gè)一一映射叫做一個(gè)置換例如:

說明

(1)將S中的元素ai寫在上一行(順序可任意),ai

的象寫在ai

之下,同一列的兩個(gè)元素的相對(duì)關(guān)系只要保持不變,即f(ai

)=aki,不同形式的寫法都認(rèn)為是同一個(gè)置換.如:

(2)置換就是將n個(gè)元的一種排列變?yōu)榱硪环N排列.

(3)n元集S共有n!種不同的置換.

定義6.2.2兩個(gè)置換p1、p2的乘積p1p2

定義為先做置換p1再做p2的結(jié)果.

例如,對(duì)于S={1,2,3,4},

一般來說,置換的乘法不滿足交換律,即p1、p2≠p2p1,如上例中

求復(fù)合置換的一種技巧就是更改p2各列的前后次序,使其第一行的排列與前者p1第二行的排列相同,那么復(fù)合置換p1、p2的第一行就是p1的第一行,其第二行是p2的第二行.如上例:

定理6.2.1設(shè)Sn是n元集合上的所有置換構(gòu)成的集合,則Sn關(guān)于置換的乘法構(gòu)成群,稱為n次對(duì)稱群.

證不失一般性,設(shè)S={1,2,…,n}.由置換乘法的定義知,封閉性、結(jié)合律顯然成立.其次,單位元為恒等置換

逆元素

【例6.2.1】將頂點(diǎn)分別為1,2,3的正三角形(見圖6.2.1)繞重心O沿逆時(shí)針方向分別旋轉(zhuǎn)0°、120°、240°,視其為頂點(diǎn)集{1,2,3}的置換,則有旋轉(zhuǎn)對(duì)稱映射圖6.2.1S3與正三角形的對(duì)應(yīng)示意圖

另一類是反射對(duì)稱映射,即將三角形123分別繞對(duì)稱軸1A、2B、3C翻轉(zhuǎn)180°得頂點(diǎn)集的另一類置換

【例6.2.2】(正方形對(duì)稱群)考察使正多邊形回到原來位置的所有可能的逆時(shí)針旋轉(zhuǎn)和翻轉(zhuǎn)動(dòng)作,可以得到一個(gè)群,稱為二面體群(參見圖6.2.2).圖6.2.2正方形的剛體變換與4次置換群

第一類:旋轉(zhuǎn)對(duì)稱關(guān)系

第二類:反射對(duì)稱關(guān)系

定義6.2.3

n次對(duì)稱群的子群稱為(n次)置換群.

定義6.2.4設(shè)置換p將集合S中的a1換為a2,a2換為a3,……,ak-1換為ak,ak換為a1,稱p為k階循環(huán)置換(或輪換),記為(a1a2…ak)或(a1,a2,…,ak).

定義6.2.5設(shè)輪換p1=(a1,a2,…,ar),p2=(b1,b2,…,bs),且ai、bj互不相同,稱p1與p2不相交.

定理6.2.2不相交的兩個(gè)輪換p1、p2滿足交換律,即p1p2=p2p1.

定理6.2.3任一置換都可以唯一分解為若干個(gè)互不相交的輪換之積

證對(duì)已知置換

【例6.2.3】將編號(hào)為1~52的卡片分為1~26、27~52兩組,交錯(cuò)互相插入,則這樣的交錯(cuò)插入重復(fù)8次后就會(huì)恢復(fù)到原來的卡片順序.

證第一次插入相當(dāng)對(duì)1~52作一次置換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).其中最長(zhǎng)的輪換為8階,而k階輪換重復(fù)k次后恢復(fù)原狀,故結(jié)論成立.

所以,美國(guó)的研究人員認(rèn)為,撲克牌洗7次最合適.

定義6.2.6稱2階輪換為對(duì)換(或換位).

定理6.2.4任何輪換都可以表示為若干個(gè)對(duì)換之積,但表示方式不唯一.

推論6.2.1一個(gè)置換總可以表為若干個(gè)對(duì)換的乘積.

定理6.2.5每個(gè)輪換的對(duì)換表示中,對(duì)換個(gè)數(shù)的奇偶性是唯一確定的.從而一個(gè)置換在它的不同的對(duì)換分解表示式中所含的對(duì)換個(gè)數(shù)的奇偶性是不變的.

定義6.2.7可以分解為奇數(shù)個(gè)對(duì)換之積的置換稱為奇置換,可以分解為偶數(shù)個(gè)對(duì)換之積的置換稱為偶置換

【例6.2.4】(十五子智力玩具)在一個(gè)4×4有方格的正方形盒子中放入15個(gè)可以滑動(dòng)的小方格,而正方形盒子右下角為一空格.規(guī)定方格的移動(dòng)規(guī)則是只準(zhǔn)與空格相鄰的方格移入空格,那么,無論怎么變動(dòng),不可能由狀態(tài)(a)中的初始“布局”變換為狀態(tài)(b)中的布局(見圖6.2.3).圖6.2.3十五子智力游戲

定理6.2.6當(dāng)n≥2時(shí),Sn中偶置換的全體構(gòu)成一個(gè)n!/2階的子群,稱為交代群,記為An.

證先證An為群.

(1)封閉性:設(shè)p1,p2∈An,顯然p1p2∈An,因?yàn)閷⒍叻纸獾慕Y(jié)果相乘,仍得偶數(shù)個(gè)對(duì)換的乘積.

(2)結(jié)合律:An?Sn,故An中元素自然滿足結(jié)合律;

(3)單位元:因Sn中單位元e本身就是偶置換,故e∈An;

6.3.1共軛類

定義6.3.1若n次置換p可分解為互不相交的λ1個(gè)1輪換,λ2個(gè)2輪換,……,λn個(gè)n輪換,則稱p屬于(λ1,λ2,…,λn)類型,或1λ12λ2…nλn型.

類型1λ12λ2…nλn也稱為格式.

顯然

6.3伯恩賽德(Burnside)引理

定義6.3.2置換群G中屬于同一類型(λ1,λ2,…,λn)的全體置換,叫做與該類型相應(yīng)的共軛類,記為D(λ1,λ2,…,λn).

【例6.3.3】將S3按共軛情況分類的結(jié)果見表6.3.1

【例6.3.4】4次置換群G={(1)(2)(3)(4),(12),(34),(12)(34)},共有3個(gè)共軛類:

其中第2類含2個(gè)置換

定理6.3.1在n元對(duì)稱群Sn中,

證設(shè)置換p為(λ1,λ2,…,λn)型,將p用輪換表示為

(λn≤1)將n個(gè)元素1,2,…,n按上格式填入λi≠0的輪換中,應(yīng)有n!種填法.但對(duì)同一置換p,在計(jì)數(shù)時(shí)被重新統(tǒng)計(jì).其原因有二:

(1)一個(gè)k輪換有k種不同表示形式;

(2)λk個(gè)k輪換間互換位置,有λk!種情形.

故p被重復(fù)統(tǒng)計(jì)λ1!λ2!…λk!1λ12λ2…nλn次,定理得證.

【例6.3.5】對(duì)稱群S3共有3個(gè)共軛類,即

實(shí)際結(jié)果見例6.3.3.

6.3.2不動(dòng)置換類

定義6.3.3設(shè)G是集合S={1,2,…,n}上的一個(gè)置換群,k∈S,p∈G,若p(k)=k,即置換p將k變?yōu)閗,則稱k為p的不動(dòng)點(diǎn).G中所有以k為不動(dòng)點(diǎn)的全體置換,構(gòu)成G的一個(gè)子集,稱為k的不動(dòng)置換類(k=1,2,…,n),記為Zk.

定理6.3.2群G中關(guān)于k的不動(dòng)置換類Zk

構(gòu)成一個(gè)子群.

證

(1)封閉性:若P1,P2∈Zk,則pi(k)=k,i=1,2,從而p1p2(k)=p2(p1(k))=p2(k)=k,即p1p2∈Zk.同理可證p2p1∈Zk;

(2)結(jié)合律:由于Zk?G,故結(jié)合律顯然成立;

(3)單位元:顯然e(k)=k,故e既是G的單位元,也是Zk的單位元;

(4)逆元素:若p∈Zk且p(k)=k,那么p的逆元一定存在,即p-1∈G而且必有p-1(k)=k,即p-1∈Zk.

由定義知,Zk是一個(gè)群.

另外,還知道|Zk|必整除|G|.

6.3.3等價(jià)類

定義6.3.4設(shè)G是集S={1,2,…,n}上的置換群,若存在i,j∈S,滿足p(i)=j,則稱i與j等價(jià),記為i~j,S中與i等價(jià)的元素的全體記為Ei,稱為元素i的“軌跡”或“蹤跡”.Ei中元素的個(gè)數(shù)稱為軌跡的長(zhǎng)度．

不難看出,元素i與j的這種等價(jià)關(guān)系滿足如下三條性質(zhì):

(1)反身性:即i~i;

(2)對(duì)稱性:若i~j,則j~i;

(3)傳遞性:若i~j,j~k,則i~k.

定理6.3.3|Ek||Zk|=|G|,k=1,2,…,n

6.3.4Burnside引理

定理6.3.4設(shè)G是n元集S={1,2,…,n}上的置換群G={p1,p2,…,pr},令λk(p)表示置換p的k階(不相交)輪換的個(gè)數(shù),則G在S上誘導(dǎo)出的等價(jià)關(guān)系將S分為不同等價(jià)類的個(gè)數(shù)為

其中λ1(p)為置換p中不動(dòng)點(diǎn)(即1階輪換)的個(gè)數(shù).圖6.3.1正方形的2染色

【例6.3.11】制作5位數(shù)的十進(jìn)制卡片(小于10000的數(shù)前面補(bǔ)0).其中某些不同的數(shù)可以合用一張卡片,例如數(shù)字0,1,6,8,9倒轉(zhuǎn)180°后認(rèn)為還是可讀的,像18609倒轉(zhuǎn)后讀做60981.這樣,共需多少?gòu)埧ㄆ纯杀硎舅械?位數(shù)?

【例6.3.12】用黃珠和藍(lán)珠穿成長(zhǎng)度為2的直線形珠串,如果顛倒一個(gè)珠串的兩端而得到另一個(gè)珠串,則認(rèn)為二者相同,求不同的珠串?dāng)?shù).

解不考慮等價(jià)時(shí),所有可能的珠串有{bb,by,yb,yy}=S,置換群G={p1=e,p2=顛倒置換}.即

所以,不同珠串?dāng)?shù)為

即bb,by,yy.

6.4Pólya定理

Burnside引理的前提是要列出各種涂色方案,方可利用置換的性質(zhì)將方案分為不同的等價(jià)類進(jìn)行計(jì)數(shù).當(dāng)被染色的對(duì)象的個(gè)數(shù)n或顏色數(shù)m較大時(shí),問題就變得非常復(fù)雜,且工作量很大,因?yàn)槭紫雀鞣N染色方案共有mn

個(gè),一個(gè)個(gè)枚舉出來是比較困難的;其次還要找出在各種置換下互相等價(jià)的方案可能更加困難,故W.Burnside自1911年提出Burn-side引理以來,該引理在計(jì)數(shù)問題中未得到廣泛應(yīng)用.

問題設(shè)有n個(gè)對(duì)象,今用m種顏色對(duì)其染色,其中每個(gè)對(duì)象任涂一種顏色,問有多少種不同的染色方案.其中,對(duì)n個(gè)對(duì)象作某一置換,若其中一種染色方案變?yōu)榱硪环N方案,則認(rèn)為該兩個(gè)方案是相同的,或者說是等價(jià)的.

從集合與置換的角度來描述這個(gè)問題則是:S是有n個(gè)元素的集合,Q是S上的置換群,C是m種顏色的集合,用C中的顏色對(duì)S中的元素染色,對(duì)每個(gè)元素任選一色染之,共有多少種不等價(jià)的方案?

兩種方案稱為等價(jià):指存在q∈Q,將S中元素的一種染色方案變?yōu)榱硪环N方案.

例如:q1有4個(gè)輪換因子,將每個(gè)輪換因子中的頂點(diǎn)染以某種顏色,由于每個(gè)輪換因子可選兩色之一,故共得24=16種方案,它恰好對(duì)應(yīng)CS中在不動(dòng)置換p1作用下的λ1(p1)=16種方案,而且可以看出在恒等置換p1作用下,16種染色方案確實(shí)不等價(jià).

同理,q2只有一個(gè)輪換因子,即4個(gè)元素涂同一種顏色,共有21=2種涂法(一般情況下,使用m種顏色,應(yīng)為m種涂法),對(duì)應(yīng)CS中在p2作用下不變的方案f1、f2.其它情形依此類推

總之,由上面的討論,可以得到以下結(jié)論:

(1)λ1(pi)=2λ(qi),i=1,2,3,4.

(2)|G|=|Q|.

定理6.4.1(Pólya定理)設(shè)Q是n個(gè)對(duì)象的一個(gè)置換群,用m種顏色涂染這n個(gè)對(duì)象,一個(gè)對(duì)象涂任意一種顏色,則在Q作用下不等價(jià)的方案數(shù)為

【例6.4.1】用紅、黃、藍(lán)三色對(duì)等邊三角形的頂點(diǎn)著色,共有多少種不同方案?解設(shè)針對(duì)S={1,2,3}的置換群為

所求不等價(jià)的方案數(shù)為

所有著色方案見圖6.4.1.圖6.4.1三角形頂點(diǎn)的3染色方案(互不等價(jià))

若置換群為Q2={(1)(2)(3),(123),(132)},即只有旋轉(zhuǎn),沒有翻轉(zhuǎn),則不等價(jià)的方案數(shù)

比在Q1作用下的著色方案多了一個(gè),即此時(shí)除了圖6.4.2的10種涂法外,還有一種如圖6.4.3所示的涂法,它是圖6.4.2中最后一種涂法翻轉(zhuǎn)過來的情形.由于Q2不含相應(yīng)于翻轉(zhuǎn)的置換,故在Q2作用下,二者不等價(jià).圖6.4.2僅有旋轉(zhuǎn)置換時(shí)增加的不等價(jià)方案

若改為用4種顏色染色,則

【例6.4.2】用兩種顏色給正立方體的8個(gè)頂點(diǎn)著色,試問有多少種不同的方案.

解使正立方體重合的關(guān)于頂點(diǎn)的運(yùn)動(dòng)群是(參見圖6.4.3):

(1)單位元(1)(2)(3)(4)(5)(6)(7)(8),格式為(1)8;

(2)繞xx'軸旋轉(zhuǎn)±90°,可得兩個(gè)置換分別為(1234)(5678)和(4321)(8765),格式為(4)2,同類的置換共有6個(gè);

(3)繞xx'軸旋轉(zhuǎn)180°,可得置換為(13)(24)(57)(68),格式為(2)4,同類的置換有3個(gè);．

(4)繞yy'軸旋轉(zhuǎn)180°,可得置換為(17)(26)(35)(48),格式為(2)4,同類的置換有6個(gè);

(5)繞zz'軸旋轉(zhuǎn)±120°,可得兩個(gè)置換分別為(136)(475)(8)(2)和(631)(574)(2)(8),格式為(1)2(3)2,同類置換有8個(gè).

由Pólya定理,不同的染色方案數(shù)為圖6.4.3正方體8個(gè)頂點(diǎn)的置換示意

6.5母函數(shù)型的Pólya定理

母函數(shù)型的Pó方lya案定進(jìn)理行也枚稱舉為.帶權(quán)的Pólya定理,它主要用于帶有限制條件的染色方案問題或?qū)唧w的方案進(jìn)行枚舉.

首先,考慮用4種顏色涂3個(gè)編號(hào)分別為1、2、3的球,設(shè)顏色為b(藍(lán))、g(綠)、r(紅)、y(黃).為了“詳細(xì)枚舉”各種涂色方案,用bi表示第i號(hào)球涂藍(lán)色,gi表示第i號(hào)球涂綠色,……,那么,用4種顏色染3個(gè)球的各種方案可表示如下:

右邊的每一項(xiàng)都代表一種染色方案,且各種方案互不相同,即互不等價(jià).例如b1r2g3表示1號(hào)球涂藍(lán)色,2號(hào)球涂紅色,3號(hào)球涂綠色;而b1r2b3則表示1、3號(hào)球涂藍(lán)色,2號(hào)球涂紅色.欲知總共有多少種不等價(jià)的方案,也就是統(tǒng)計(jì)上式右邊有多少項(xiàng).只要在等式右端令bi=gi=ri=yi=1(i=1,2,3)就可得染色方案總數(shù)L.為方便計(jì)算,從左端看,有

若只關(guān)心某方案用了哪些顏色,不關(guān)心具體對(duì)象染了什么顏色,即將各種方案按使用顏色情況“分類枚舉”,或稱“分類統(tǒng)計(jì)”.例如欲知道2個(gè)球染藍(lán)色、1個(gè)球染綠色的方案有多少個(gè),那么,展開多項(xiàng)式

下面考慮分組染色的方案數(shù).問題來源于Pólya定理的推導(dǎo)過程.如上一節(jié)中用m種顏色對(duì)構(gòu)成大正方形的4個(gè)相同的小正方形進(jìn)行染色,大正方形的空間變換為置換q2={旋轉(zhuǎn)180°},那么,只有當(dāng)小正方形1和3同色,2和4同色時(shí),才能保證在q2作用下,所染的方案保持不變.這實(shí)質(zhì)上就是將不同的球先分組,同一組的球顏色相同,求不等價(jià)的染色方案數(shù).

個(gè)用3種顏色b(藍(lán)色)、r(紅色)、y(黃色)染4個(gè)不同的球,將4個(gè)球分為2組,每組2個(gè)，要求同組的球同色(如1、3號(hào)球?yàn)榈谝唤M,2、4號(hào)球?yàn)榈诙M),各種方案的詳細(xì)枚舉情況如下:

【例6.5.1】用三種不同顏色的珠子穿成4個(gè)珠子的項(xiàng)鏈,共有多少不同的方案?

解如圖6.5.1所示,使之重合的運(yùn)動(dòng)有關(guān)于圓環(huán)中心旋轉(zhuǎn)±90°和±180°,以及關(guān)于xx'和yy'軸翻轉(zhuǎn)180°.故有置換群G={p1,p2,…,p8},其中圖6.5.1四珠項(xiàng)鏈的幾何變換圖6.5.2兩藍(lán)、一紅一綠珠子組成的不等價(jià)的項(xiàng)鏈

【例6.5.2】由4顆紅色的珠子嵌在正六面體的4個(gè)角,試問有多少種方案.圖6.5.3正方體頂點(diǎn)兩種顏色數(shù)相等的2染色

6.6應(yīng)用

【例6.6.1】將兩個(gè)相同的白球和兩個(gè)相同的黑球放入兩個(gè)不同的盒子里,問有多少種不同的放法.列出全部方案.又問每盒中有兩個(gè)球的放法有多少種.

解這是一個(gè)典型的球分類相同的分配問題.即將4個(gè)球放入兩個(gè)不同的盒子,但4個(gè)球既不是全相同,也不是全不同,而是分類相同.

又如將題目改為白球兩個(gè)、黑球3個(gè),則相應(yīng)的置換群為

【例6.6.2】用紅、黃、藍(lán)三種顏色對(duì)正六邊形的頂點(diǎn)進(jìn)行著色,共有多少種不同的方案?其中正六邊形可以繞幾何中心旋轉(zhuǎn)或沿其對(duì)稱軸翻轉(zhuǎn).

解圖6.6.1的正六邊形可以分別繞其中心O逆時(shí)針旋轉(zhuǎn)0°、60°、120°、180°、240°、300°以及過3對(duì)頂點(diǎn)、3個(gè)對(duì)稱邊的中點(diǎn)連線翻轉(zhuǎn),從而得置換群Q所含的置換如下:圖6.6.1正六邊形頂點(diǎn)的置換示意

【例6.6.3】3個(gè)布爾變量x1,x2,x3的布爾函數(shù)裝置(見圖6.6.2)有多少種不同的結(jié)構(gòu)?圖6.6.23個(gè)輸入端的布爾裝置

由此可得各種狀態(tài),即集合S的置換群Q為

求不同布爾函數(shù)裝置的問題,相當(dāng)于求服從群Q的變換的8個(gè)頂點(diǎn)a0,a1,a2,a3,a4,a5,a6,a7用兩種顏色(相當(dāng)于布爾函數(shù)的0、1狀態(tài))對(duì)之著色的方案數(shù).故由Pólya定理,有

種方案.也就是說,三個(gè)變量的256個(gè)布爾函數(shù)中,只有80個(gè)是不等價(jià)的,其余的函數(shù)可通過改變輸入端的順序而得到.

【例6.6.4】用紅、藍(lán)兩色給正立方體的六個(gè)面著色,可得多少種不同方案?

解將正方體的上、下、左、右、前、后6個(gè)面分別編號(hào)為1、6、4、2、3、5,使正立方體的面重合的剛體運(yùn)動(dòng)群有以下幾種情況(參見圖6.6.3):

(1)不動(dòng)置換:即單位元素(1)(2)(3)(4)(5)(6),格式為(1)6;

(2)繞過(1)和(6)面中心的AB軸旋轉(zhuǎn)±90°(圖6.6.3(a)),對(duì)應(yīng)置換為(1)(2345)(6),(1)(5432)(6),格式為(1)2(4)1.類似的面共有3對(duì),故這種格式的置換共有6個(gè);

(3)繞AB軸旋轉(zhuǎn)180°的置換為(1)(24)(35)(6),格式為(1)2(2)2,同類的置換有3個(gè);

(4)繞CD軸旋轉(zhuǎn)180°(圖6.6.3(b))的置換為(16)(25)(34),格式為(2)3,而正立方體對(duì)角線位置的平行的棱有6對(duì),故同類置換有6個(gè);

(5)繞對(duì)角線EF旋轉(zhuǎn)±120°(圖6.6.3(c))的置換分別為(346)(152)和(643)(251),格式都是(3)2.這樣的對(duì)角線有4個(gè),即同類置換有8個(gè).

所以,不同的染色方案為圖6.6.3