群論解決計(jì)數(shù)問題的一個(gè)教學(xué)改進(jìn)

王麗杰， 王慶先

(1.電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，成都611731；2.電子科技大學(xué) 信息與軟件工程學(xué)院,成都610054)

1 引 言

群論是近世代數(shù)中非常重要的理論，滲入現(xiàn)代數(shù)學(xué)、物理、化學(xué)和計(jì)算機(jī)等學(xué)科的方方面面[1-4].例如，可應(yīng)用群論解決一般情況下難以求解的計(jì)數(shù)問題，包含項(xiàng)鏈問題、正多面體著色問題、圖和開關(guān)電路的同構(gòu)計(jì)數(shù)問題等[5].對于這些計(jì)數(shù)問題的求解，現(xiàn)有的近世代數(shù)教材都是先講解群對集合的作用和軌道這兩個(gè)概念，再推導(dǎo)伯恩賽德引理，最后再利用伯恩賽德引理來解決特定的計(jì)數(shù)問題[5-6].有的教材甚至完全沒有講到計(jì)數(shù)問題的求解[7-8].這些概念定理都很晦澀難懂，因而學(xué)生理解起來非常困難.在本科階段，考慮到難度，離散數(shù)學(xué)教材一般會直接省略這部分內(nèi)容.但是，群論本身已經(jīng)是很抽象的理論，如果能夠在教學(xué)過程中引入利用群論解決計(jì)數(shù)問題的實(shí)際應(yīng)用，讓學(xué)生體會到群論的魅力，可有效的提升教學(xué)體驗(yàn).因而，本文討論直接利用置換群知識解決一種典型的計(jì)數(shù)問題——項(xiàng)鏈問題，然后可將其引申到伯恩賽德定理.這樣，學(xué)生可在缺少相關(guān)理論基礎(chǔ)，僅學(xué)習(xí)了置換群的情況下理解計(jì)數(shù)問題的求解思路.而需要進(jìn)一步學(xué)習(xí)的學(xué)生，也能夠?qū)τ谌簩系淖饔煤蛙壍纼蓚€(gè)概念有更加形象直觀的認(rèn)識，對于理解和運(yùn)用伯恩賽德定理解決類似的計(jì)數(shù)問題會有非常大的好處，從而形成教學(xué)邏輯的平滑過渡.

2 項(xiàng)鏈問題及二面體群描述

項(xiàng)鏈問題可形象的描述為，用n種顏色的珠子做成有m顆珠子的項(xiàng)鏈，問可做成多少種本質(zhì)上不同的項(xiàng)鏈？

首先將這個(gè)問題轉(zhuǎn)化為數(shù)學(xué)形式.m顆珠子做成一個(gè)項(xiàng)鏈，可用一個(gè)正m邊形來表示，每個(gè)頂點(diǎn)代表一顆珠子.從任意一個(gè)頂點(diǎn)開始，沿逆時(shí)針方向，每個(gè)頂點(diǎn)用1,2,…,m來標(biāo)號.這樣的一個(gè)有標(biāo)號項(xiàng)鏈中，每一顆珠子有n種選擇，所以總共有nm種.但是，有一些其實(shí)本質(zhì)上是一樣的，比如旋轉(zhuǎn)一個(gè)角度或者翻轉(zhuǎn)后就會重合.若只考慮本質(zhì)上不同的項(xiàng)鏈，當(dāng)n和m數(shù)值較大時(shí)，則很難用簡單的枚舉方法來解決.群論方法是當(dāng)前解決這一類問題最為簡單和有效的方法，即利用二面體群來求解.

考慮正m邊形在三維空間中保持各頂點(diǎn)相對位置不變的旋轉(zhuǎn)或翻轉(zhuǎn)變換，可簡稱RFT(Rotate-Flip Transformation).每個(gè)RFT對應(yīng)其頂點(diǎn)集合的一個(gè)置換，兩個(gè)置換的乘積就是一個(gè)RFT接著另一個(gè)RFT，一個(gè)RFT的逆就是其反向RFT，因此，所有RFT構(gòu)成一個(gè)群，這個(gè)群是m次對稱群Sm的子群，也是一個(gè)置換群，通常稱為二面體群，記為Dm.

接下來給出二面體群Dm的一般表達(dá)形式.設(shè)X={1,2,…,m}為正m正邊形的頂點(diǎn)集合，且按逆時(shí)針方向排列，如圖1所示.

圖1 正m邊形的變換

正m邊形有兩種旋轉(zhuǎn)方式：繞中心O沿逆時(shí)針方向旋轉(zhuǎn)和關(guān)于一條對稱軸進(jìn)行翻轉(zhuǎn).

將正多邊形繞中心O沿逆時(shí)針方向旋轉(zhuǎn)2kπ/m度(k=0,1,2,…,m-1)，則得到m個(gè)變換，可用輪換表示為

ρk=(1 2 3 …m)k,k=0,1,…,m-1，

而若將正多邊形繞圖1所示的對稱軸l0,l1,…,lm-1翻轉(zhuǎn)角度π，同樣得到m個(gè)變換，使用輪換表示為

π0=(2m)(3m-1)…，

πk=π0ρk,k=0,1,2,…,m-1，

因此，二面體群可表示為

Dm={ρk,πk|k=0,1,2,…,m-1}.

3 僅利用置換群知識解決項(xiàng)鏈問題

首先假設(shè)集合Ω={a1,a2,a3,…}表示所有項(xiàng)鏈樣式的集合，即|Ω|=nm.每個(gè)項(xiàng)鏈樣式經(jīng)過二面體群Dm中的任何一種置換后可變換成另一種樣式，可用數(shù)學(xué)形式描述為

?ai∈Ω,g∈Dm, ?aj∈Ω,g(ai)=aj.

設(shè)Ω中本質(zhì)上不同的項(xiàng)鏈有N種，由于每一種樣式都有2m種方式進(jìn)行變換，可選擇其中任何一個(gè)作為代表樣式，記為Δ={b1,b2,…,bN}，顯然Δ?Ω.

圖2 項(xiàng)鏈樣式的變換

顯然，可得到如下事實(shí)：

事實(shí)1C11,C12,…,CN(2m)包含了Ω中所有元素.

證顯然成立，否則Δ={b1,b2,…,bN}不能包含所有本質(zhì)上不同的項(xiàng)鏈樣式.

事實(shí)2當(dāng)i≠j，則Mi與Mj不相交，即Mi∩Mj=?.

證反證法.假設(shè)Mi∩Mj≠?，即?x∈Mi∩Mj，所以?g,h∈Dm，使得g(bi)=x,h(bj)=x.由于i≠j，即有bi和bj本質(zhì)上不同.但x=g(bi)=h(bj)，可見bi=g-1h(bj)，這說明bj經(jīng)過置換g-1h變換之后成為bi，可見bi∈Mj，這說明bi和bj本質(zhì)上是相同的.出現(xiàn)矛盾，事實(shí)2得證.

由事實(shí)1及圖2，可知：對?ai∈Ω,?g∈Dm,bj∈Δ，使得g(bj)=ai.其中i∈{1,2,3,…,nm},j∈{1,2,3,…,N}.此時(shí)令集合Bij={g|g∈Dm,g(bj)=ai}，這里j取值是特定的.易知Bij≠?.又由事實(shí)2，得到ni=|Bij|.而為了求出|Bij|，需要引入下面的事實(shí)3和事實(shí)4.

事實(shí)3令A(yù)i={g|g∈Dm,g(ai)=ai},i∈{1,2,3,…,nm}，則Ai是Dm的一個(gè)子群.

證Dm有單位元ρ0,ρ0表示逆時(shí)針旋轉(zhuǎn)0度，即ρ0(ai)=ai，從而ρ0∈Ai.又對?g,h∈Ai，則有g(shù)(ai)=ai，h(ai)=ai，即gh-1(ai)=ai，從而gh-1∈Ai.所以，Ai是Dm的一個(gè)子群.

事實(shí)4|Ai|=|Bij|,i∈{1,2,3,…,nm},j∈{1,2,3,…,N}.

證可通過在Ai和Bij之間建立一個(gè)雙射來證明.根據(jù)事實(shí)3，Ai是Dm的一個(gè)子群，從而有單位元ρ0∈Ai.由于Bij≠?，因此必然存在某一置換g∈Bij，使得g(bj)=ai.

建立映射f∶Ai→Bij，對于?h∈Ai，令f(h)=hg.由于hg(bj)=h(g(bj))=h(ai)=ai，所以hg∈Bij.根據(jù)群的消去律，可知f是單射.又對?δ∈Bij，由于δ(bj)=ai,g-1(ai)=bj,可知δg-1(ai)=δ(g-1(ai))=δ(bj)=ai.從而?δg-1∈Ai，使得f(δg-1)=δg-1g=δ.即f是滿射.所以，f是Ai到Bij的雙射，從而|Ai|=|Bij|.

|Ai|直觀上表示的是對項(xiàng)鏈樣式ai進(jìn)行變換后仍然得到ai的置換數(shù)量.考慮如下函數(shù)：ψ:Ω×Dm→{0,1}，對

根據(jù)以上推導(dǎo)，得到項(xiàng)鏈問題的最終解法.本質(zhì)上不同的項(xiàng)鏈個(gè)數(shù)為

例1用3種顏色做成有6顆珠子的項(xiàng)鏈，可做多少種不同的項(xiàng)鏈?

解這里n=3,m=6, 對應(yīng)二面體群為D6.D6中有12個(gè)元素，ρ0是16型，ρ1和ρ5是61型，ρ2和ρ4是32型，ρ3是23型，πk(k=0,1,…,5)則有3個(gè)1222型及3個(gè)23型.所以總共有1個(gè)16型置換，3個(gè)1222型置換，4個(gè)23型置換，2個(gè)32型置換，2個(gè)61型置換.從而

即總共有92種本質(zhì)上不同的項(xiàng)鏈.

綜上，基于置換群給出了項(xiàng)鏈問題的解法.

4 伯恩賽德引理的引申

對于伯恩賽德引理有進(jìn)一步學(xué)習(xí)需求的學(xué)生，也可在理解了上面的項(xiàng)鏈問題解法之后，引申出群對集合的作用及軌道相關(guān)的概念，并得到伯恩賽德引理.表1給出相關(guān)概念定理的對應(yīng)關(guān)系.

表1 伯恩賽德引理相關(guān)概念的對應(yīng)

5 結(jié) 論

本文提供了計(jì)數(shù)問題的低難度解法，使得教師可在不引入群對集合的作用和軌道兩個(gè)概念及伯恩賽德定理的情況下講解群論的實(shí)際應(yīng)用，增加課堂趣味性和有效性.同時(shí)，還可以更順利的引入這些重要但抽象的概念和定理，從而提升教學(xué)體驗(yàn).作者已在近世代數(shù)和離散數(shù)學(xué)課堂講授中應(yīng)用了這些思路，取得了較好的教學(xué)效果.

致謝作者非常感謝相關(guān)文獻(xiàn)對本文的啟發(fā)以及審稿專家提出的寶貴意見.