王麗杰， 王慶先

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

1 引 言

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

2 項鏈問題及二面體群描述

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

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

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

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

圖1 正m邊形的變換

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

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

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

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

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

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

因此，二面體群可表示為

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

3 僅利用置換群知識解決項鏈問題

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

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

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

圖2 項鏈樣式的變換

顯然，可得到如下事實：

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

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

事實2當i≠j，則Mi與Mj不相交，即Mi∩Mj=?.

證反證法.假設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)矛盾，事實2得證.

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

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

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

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

證可通過在Ai和Bij之間建立一個雙射來證明.根據(jù)事實3，Ai是Dm的一個子群，從而有單位元ρ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|直觀上表示的是對項鏈樣式ai進行變換后仍然得到ai的置換數(shù)量.考慮如下函數(shù)：ψ:Ω×Dm→{0,1}，對

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

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

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

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

綜上，基于置換群給出了項鏈問題的解法.

4 伯恩賽德引理的引申

對于伯恩賽德引理有進一步學習需求的學生，也可在理解了上面的項鏈問題解法之后，引申出群對集合的作用及軌道相關的概念，并得到伯恩賽德引理.表1給出相關概念定理的對應關系.

表1 伯恩賽德引理相關概念的對應

5 結 論

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

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