高中排列组合完结篇

《高中排列组合完结篇》由会员分享，可在线阅读，更多相关《高中排列组合完结篇（5页珍藏版）》请在金锄头文库上搜索。

1、高中排列組合完結篇 Burnside Lemma OddOddOf 一、引子 以下是一些排列組合的結果 1. 將 n 個相異物排成一列的排列數為 n!。2. 從 n 個相異物中選 m 個的組合數為 。n!m!(n - m)!3. 從 n 種物品中可重覆的取 m 種物品排成一列的排列數為 mn。 4. 從 n 種物品中可重覆的取 m 種物品的組合數；即方程 x1+x2+xn = m的非負整數解個數為。(m + n - 1)!m! (n - 1)!5. 設有 k 種物品，第 j 種有 nj個，共 n=個。將它們排成一列的排列k j = 1nj數即是將 n 個東西分到 k 個人，第 j 個人分 nj

2、個的方法數為 。n!n1! n2!nk! 以下是常見的兩個題目 題目一： n 個人坐在一圈的方法有多少種？ 題目二：n 個相異的珠子串成項鍊的方法有多少種？ 題目三：將 2n 個東西平分成兩堆的方法有多少種？答案一：(n-1)! 答案二： (n2)，1(n=1,2) 答案三：(n - 1)!2(2n)!n!n!2如果你覺得題目一答案是 n!，或是覺得題目一和題目二一樣，那你就上當 了。沒有關係，只要這次把原因弄清楚，下次就會了。 冥王星文版 總是可以先考慮把位置編號，如此一來，我們知道，其實所有的可能不外 乎是這 n!個情形。但是我們不會把這 n!個全部都分別出來，事實上，有好多個 情形其實要

3、算做同一種。好在這個規則並不是隨意的，事實上，我們稱兩個情 形 x 和 y 為同一種當且僅當存在一個可以接受的變換 g，使得 g(x)=y。對於題目一來說，所有可接受的變換即是繞著圓圈轉。 對於題目二來說，所有可接受的變換除了繞著圓圈轉，還有整個翻過來。二、群 在代數上，定義群是如下的結構。 定義：群定義：群(group) 設 G 為一個集合，為其上的一個運算，(即：GG G )若 有結合律：即對所有 G 中的 a,b,c，(ab)c = a(bc)； 且有單位元素：即在 G 中存在 e，使得對所有 G 中的 a，ae=a=ea； 且所有 G 中的 a 都有反元素：即存在 a-1使得 aa-1

4、 = e = a-1a。 則稱(G,)為一群，在很清楚時，也簡稱 G 為一群。 這個群就是我們即將拿來當做可接受的變換 。 例： 這幾個是日常生活中很直觀的群(。表示函數合成)。 (平面上平移,。)、(平面上平移旋轉,。)、(平面上平移旋轉鏡射(剛體運動), 。) (空間中繞原點旋轉,。) 這些群的集合 G 都是從某個集合 A 送到自己的函數所成的集合，運算都是 函數合成，這其實是一個很自然的結果，因為函數合成會滿足結合律。 現任取 A 非空，G 就取所有 AA 的可逆函數，即一對一且映成函數，這 樣 (G,。)就變成一個群記成 SA，若 A=1,2,n我們稱為 n 階對稱群 Sn。 再看看我

5、們剛才的例子，(平面上平移,。) (平面上平移旋轉,。)(平 面上平移旋轉鏡射(剛體運動),。) S平面。發現前面的集合是一個包含一個， 而且集合較大的運算和集合較小的一致。一般來說若有兩個群 (H,)和(G,)。 若 H 包含於 G，且對所有 H 中的 a,b，ab = ab。則稱(H,)為(G,)的子群， 記(H,)(G,)，也簡記為 HG。 對於 S平面和 S空間有一類特別的子群。 設 X 為平面上的一個圖形，G=f:平面平面|f 可逆、f(X)=XS平面。 設 Y 為空間中的一個圖形，H=f:空間空間|f 可逆、f(Y)=YS空間。 此外：G平面上平移旋轉 G平面上平移旋轉鏡射S平面。

6、H空間中繞原點旋轉 S空間。 要檢查子群可以用下面這個定理： 定理：定理： 設設 G 為群，為群，H 為子集，則為子集，則 H 為為 G 的子群若且唯若的子群若且唯若 H 非空，對所有非空，對所有 H 中的中的 a,b，ab 屬於屬於 H 且且 a-1屬於屬於 H。 設設 G 為群，為群，H、K 為其子群，則為其子群，則 HK 亦是其子群亦是其子群 在上面的例子中，若是取 X 為中央為原點的正 n 邊形(的頂點)，設一個頂 點在 x 軸上，取 Y 為中央為原點的正多面體(的頂點)。則可以想像G平面上平移旋轉=繞原點轉|k=0,1,n-1=rk| k=0,1,n-1(記2knr 為繞原點轉)，這

7、個群叫循環群，記成 Cn。2nG平面上平移旋轉鏡射=繞原點轉、先對 x 軸翻轉再繞原點轉2kn|k=0,1,n-1=rk , rkd | k=0,1,n-1 (記對 x 軸翻轉為 d) ，這個群叫二面2kn體群，記成 Dn。三、群的作用(group action) 定義：群的作用定義：群的作用(group action) 設 G 為群(運算記號省略)，X 為一個集合，：GXX 若滿足對所有 g,h 屬於 G、x 屬於 X，g(hx) = ghx、ex=x 則稱為 G 在 X 上的作用，又稱 G 作用在 X 上。 例： 任一群 G，都可以作用在任一集合 X，只要定義 gx=x 即可。 對非空集合

8、 A，SA可以作用在 A 上，即 fa = f(a) 平面上平移、平面上平移旋轉、平面上平移旋轉鏡射可以作用在平面上。設 P 為平面上的一個圖形，G=f:平面平面|f 可逆、f(P)=P、G平面上平移 旋轉、G平面上平移旋轉鏡射可以作用在 P 上。 設 Q 為空間中的一個圖形，H=f:空間空間|f 可逆、f(Q)=Q、H空間中繞 原點旋轉可以作用在 Q 上。特別的 Cn、Dn都可以作用在正多邊形(的頂點)上。定義：軌道定義：軌道(orbit)、stabilizer、不動點、不動點(fixed point) 設 G 作用在 X 上。 對每一個 X 中的 x 定義軌道 O(x) = gx | g

9、屬於 G即 x 在 G 作用下所有可能 的變成的元素。 對每一個 X 中的 x 定義 stabilizer G(x) = g 屬於 G| gx=x即所有不會動到 x 的元素。 對每一個 G 中的 g 定義不動點 F(g) = x 屬於 X| gx=x即在 g 作用下不動的 x。 定理：定理： 設設 G 作用在作用在 X 上。上。 對所有對所有 X 中的中的 x，G(x)是是 G 的子群的子群 對所有對所有 X 中的中的 x,y，若，若 x 屬於屬於 O(y)，則，則 y 屬於屬於 O(x)、O(x)=O(y)。 對所有對所有 X 中的中的 x,y，O(x)=O(y)或或 O(x)O(y)為空集

10、合。為空集合。 若若 X 為有限集，存在為有限集，存在 x1、x2、xr使得使得 X = O1O2Or，且任兩個交集，且任兩個交集 為空集合，為空集合，Oj=O(xj)。從而。從而|X| = |O1|+|O2|+|Or| 若若 G 為有限群對所有為有限群對所有 X 中的中的 x, |G| = |O(x)| |G(x)| 四、正多面體群 到這邊，總算可以來探討前面弄不清楚的正多面體群了。 方法都是讓正多面體群作用在正多面體的面上，觀察一個面 x 的軌道 O(x)，和它的 Stabilizer，G(x)，即可求出正多面體群的大小(order)。然後我們只要找 到那麼多個變換，就表示沒有遺漏了。 正

11、四面體：|O(x)|=4；|G(x)|=3。12 種。 正方體：|O(x)|=6；|G(x)|=4；正八面體：|O(x)|=8；|G(x)|=3。24 種。 正十二面體：|O(x)|=12；|G(x)|=5；正二十面體：|O(x)|=20；|G(x)|=3。60 種。五、Burnside Lemma 定理：定理：Burnside Lemma設有限群設有限群 G 作用在有限集作用在有限集 X 上，則軌道數為上，則軌道數為 G G|F(g)|。1|G|證明： 設 S = (g,x) 屬於 GX | gx = x，則一方面|S| =G|F(g)|，另一方面，|S| = X| G(x) | =X，但

12、X = O1O2Or， 把在同一軌道的項合起來，|G|O(x) |則 r=軌道數= |F(g)|1|G|為什麼要求軌道數呢？其實從前面的說明不難看出，軌道數，就是所要求 的種數 。這個定理本身不難證，以下給出一些例子看看它的威力所在。 六、應用 (以下題目，大部分都可以推廣到一般的情形，方法一樣，不過計算很複雜) 第一題：第一題：12 個珠子，個珠子，4 個紅的，個紅的，4 個黃的，個黃的，4 個藍的，排成一圈的方法有幾種？個藍的，排成一圈的方法有幾種？ 串成項鍊的方法有幾種？串成項鍊的方法有幾種？ 第二題：用第二題：用 n 種顏色去塗正十二面體的面有幾種方法？種顏色去塗正十二面體的面有幾種方

13、法？(顏色可以重複用，也可顏色可以重複用，也可 以沒用完以沒用完)。若是用。若是用 3 種顏色，每種顏色都要用的話有幾種？種顏色，每種顏色都要用的話有幾種？ 第三題：如下圖將一個邊長為第三題：如下圖將一個邊長為 n 的正三角形切割成小塊，用的正三角形切割成小塊，用 m 種顏色在小塊上種顏色在小塊上塗色，有幾種方法？如果正三角形還可以翻過來，塗色，有幾種方法？如果正三角形還可以翻過來，(譬如用彩色玻璃紙貼框架譬如用彩色玻璃紙貼框架) 那又有幾種？那又有幾種？(顏色可以重複用，也可以沒用完顏色可以重複用，也可以沒用完)第四題：將一有第四題：將一有 a+b 等分格的圓盤塗成等分格的圓盤塗成 a 紅、

14、紅、b 藍的方法有幾種？藍的方法有幾種？ 解： 這一題展示一個較一般的結果，其實精神和第一題一樣(N)為 Euler 函數=|0nN| (n,N)=1|Ca+b=rk| k=0,1,a+b-1作用在圓盤所有的塗法(共個情形)上。(a + b)!a!b!對於 rj，因為 rj 圈結構為(a+b,j)個長度的括號，故只能選若干個紅a + b(a + b)色、若干個塗藍色，即|a 且 |b 即 |j，有種塗法。故a + b(a + b)a + b(a + b)a + b(a)(a + b) a(a + b)a + b)|F(g)| = ，記 j=k則(a+b,j) = (a,b), k)(a + b

15、) a(a + b)a + b)a + b(a)a + b(a)|F(g)| = ，記 d=(a,b), k)，則 d|(a,b)，且共有 ()個 k(a) k = 1(a + b(a)(a,b)a(a,b)(a) (a)d滿足條件，所以所求即|F(g)| =() 1a + b1a + bd|(a)(a)d(a + b(a)dad(a)七、習題 1. 用 a 個紅珠子、b 個藍珠子、c 個黃珠子串成鍊子 (但首尾沒有接起來)有幾 種？ 2. 把題目一和題目二的冥王星文版用 Burnside Lemma 做完。 3. 用 n 種顏色塗正方體的 8 個頂點有幾種方法？4. 把正四面體每一面都切成像第三題一樣，用 n 種顏色塗這些小格的方法有幾 種？正八面體呢？正二十面體呢？ 5. 第三題中，n=5，如果要塗 a 格紅色、b=25-a 格黃色的話有幾種？ 6. 用 12 個紅珠子、6 個白珠子、4 個藍珠子串成一條 24 個珠子的項鍊有幾種 方法？ 八、結語 對於不盡相異物的排列組合，高中數學只講了直線排列一種情形，其它的 情形則不予討論；但是對於完全相異物，卻有環狀排列甚至串項鍊等內容。像 第一題那種題目似乎是很容易想到，卻不大容易著手的題目。這邊用到了群， 一個很有趣的結構，來討論旋轉、翻轉等對稱性，再回來看這些題目，私以為 可以