高中排列組合完結篇 - 國立臺灣大學.doc

《高中排列組合完結篇 - 國立臺灣大學.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、高中排列組合完結篇BurnsideLemmaOddOddOf一、引子以下是一些排列組合的結果1.將n個相異物排成一列的排列數為n!。2.從n個相異物中選m個的組合數為。3.從n種物品中可重覆的取m種物品排成一列的排列數為mn。4.從n種物品中可重覆的取m種物品的組合數；即方程x1+x2+…+xn=m的非負整數解個數為。5.設有k種物品，第j種有nj個，共n=個。將它們排成一列的排列數即是將n個東西分到k個人，第j個人分nj個的方法數為。以下是常見的兩個題目題目一：n個人坐在一圈的方法有多少種？題目二：n個相異的珠子串成項鍊的方法有

2、多少種？題目三：將2n個東西平分成兩堆的方法有多少種？答案一：(n-1)!答案二：(n>2)，1(n=1,2)答案三：如果你覺得題目一答案是n!，或是覺得題目一和題目二一樣，那你就上當了。沒有關係，只要這次把原因弄清楚，下次就會了。《冥王星文版》總是可以先考慮把位置編號，如此一來，我們知道，其實所有的可能不外乎是這n!個情形。但是我們不會把這n!個全部都分別出來，事實上，有好多個情形其實要算做同一種。好在這個規則並不是隨意的，事實上，我們稱兩個情形x和y為同一種當且僅當存在一個可以接受的變換g，使得g(x)=y。對於題目一來說，所

3、有可接受的變換即是繞著圓圈轉。對於題目二來說，所有可接受的變換除了繞著圓圈轉，還有整個翻過來。二、群在代數上，定義群是如下的結構。定義：群(group)設G為一個集合，‧為其上的一個運算，(即‧：G╳GàG)若‧有結合律：即對所有G中的a,b,c，(a‧b)‧c=a‧(b‧c)；且‧有單位元素：即在G中存在e，使得對所有G中的a，a‧e=a=e‧a；且所有G中的a都有‧反元素：即存在a-1使得a‧a-1=e=a-1‧a。則稱(G,‧)為一群，在‧很清楚時，也簡稱G為一群。這個群就是我們即將拿來當做「可接受的變換」。例：這幾個是日常

4、生活中很直觀的群(。表示函數合成)。({平面上平移},。)、({平面上平移旋轉},。)、({平面上平移旋轉鏡射(剛體運動)},。)({空間中繞原點旋轉},。)這些群的集合G都是從某個集合A送到自己的函數所成的集合，運算都是函數合成，這其實是一個很自然的結果，因為函數合成會滿足結合律。現任取A非空，G就取所有AàA的可逆函數，即一對一且映成函數，這樣(G,。)就變成一個群記成SA，若A={1,2,…,n}我們稱為n階對稱群Sn。再看看我們剛才的例子，({平面上平移},。)<({平面上平移旋轉},。)<({平面上平移旋轉鏡射(剛體運動

5、)},。)

6、f可逆、f(X)=X}

7、f可逆、f(Y)=Y}

8、}

9、k=0,1,…,n-1}={rk

10、k=0,1,…,n-1}(記r為繞原點轉)，這個群叫循環群，記成Cn。G∩{平面上平移旋轉鏡射}={繞原點轉、先對x軸翻轉再繞原點轉

11、k=0,1,…,

12、n-1}={rk,rkd

13、k=0,1,…,n-1}(記對x軸翻轉為d)，這個群叫二面體群，記成Dn。一、群的作用(groupaction)定義：群的作用(groupaction)設G為群(運算記號省略)，X為一個集合，‧：G╳XàX若‧滿足對所有g,h屬於G、x屬於X，g‧(h‧x)=gh‧x、e‧x=x則稱‧為G在X上的作用，又稱G作用在X上。例：任一群G，都可以作用在任一集合X，只要定義g‧x=x即可。對非空集合A，SA可以作用在A上，即f‧a=f(a){平面上平移}、{平面上平移旋轉}、{平面上平移旋轉鏡射}可以作用在平面上

14、。設P為平面上的一個圖形，G={f:平面à平面

15、f可逆、f(P)=P}、G∩{平面上平移旋轉}、G∩{平面上平移旋轉鏡射}可以作用在P上。設Q為空間中的一個圖形，H={f:空間à空間

16、f可逆、f(Q)=Q}、H∩{空間中繞原點旋轉}可以作用在Q上。