不完全相異物之環狀排列 - 都都的網誌

字體：小中大

不完全相異物之環狀排列

2010/04/23 19:27:01瀏覽2626｜回應13｜推薦1

哈今天跟同學討論高中數學的時候

(其實本來只是討論家教而已,不知不覺就討論到大家以前高中教的內容)

這個問題之前導的有提到一下,不過並沒有著太多筆墨

就是

不完全相異物之環狀排列的問題

像是A有a個,B有b個,C有c個,......

將這些相異物做環狀排列,有幾種情況??

之前我們在做完全相異物環排的時候,會先排成一直線,在除以因為環狀而重複的效應

所以要除以總數n

如果是不完全相異物的時候,好像會和a,b,c的最大公因數有關係(?

----------------------------------------------------

另外就是

珠狀排列,要將沒有對稱的情形數目在除以2,以免多計算

但是有沒有比較有效率的方法可以塞出有對稱的晴行的數目呢??

( 知識學習｜科學百科 )

引用網址：https://classic-blog.udn.com/article/trackback.jsp?uid=ivan5chess&aid=3970241


	回應文章	第頁／共 2 頁


	陳

陳

2010/04/29 15:28

關於置換群的個數有個簡易判別法,不過還是得全找出來才行,譬如6個相異物作環狀排列,置換群為6個;若作珠狀排列,則有12個,其實就是高中所教的先除以6再除以2,因此總共除以12,所以珠狀時會有12個置換群;按照這個概念,正立方體著色時會有24個,正四面體著色時會有12個,倘若是上下底為正方形,側面為長寬不等的長方形的長方體則有8個,其實就是高中所教的(翻數)*(轉數),但是這是置換群總數,至於有哪些,則一定得一一全列出來做計算,但是雖然如此,如果確定置換群總數,則不失為一個檢查是否有遺漏的好方法!!

都都(ivan5chess) 於 2010-04-29 21:46 回覆：

嗯嗯了解~

想了一陣子大概知道它的原理了

之前還上網查了一些群論的資料

感覺好像會把問題弄得更複雜哈哈


	陳

陳

2010/04/28 00:24

我給一些例子,這樣應該比較容易體會:
波利亞定理(Polya’s theorem):
aabb環狀排列數:(先將位置按順時針編號,分別為1234四個位置)
置換群分別為:
(1)(2)(3)(4):此即為每個位置都不動,注意括號中必須全為相同,所以aabb放入方法數為4!/(2!)(2!)=6種
(1234):此即為順時針轉一格,所以1到2到3到4,但aabb填入時無法使每個括號中全為相同,故方法數0種
(13)(24):此為順時針轉二格,所以1到3,2到4,aabb填入時方法數為2!=2種
(1432):此為順時針轉三格,所以1到4到3到2,但aabb填入時無法使每個括號中全為相同,故方法數0種
所求即為(所有方法數)/(置換群個數)=(6+2)/4=2種

aabb珠狀排列數:
除了上述的置換群之外,尚有:
(1)(3)(24):此即1,3號位置不動,2,4號位置互換,形同翻轉180度,aabb填入時有2*1=2種
(2)(4)(13):此即2,4號位置不動,1,3號位置互換,形同翻轉180度,aabb填入時有2*1=2種
(12)(34):此即1,2號位置互換,3,4號位置互換,亦為翻轉180度,aabb填入時有2!=2種
(23)(14):此即2,3號位置互換,1,4號位置互換,亦為翻轉180度,aabb填入時有2!=2種
所求即為(所有方法數)/(置換群個數)=(6+2+2+2+2+2)/8=2種

其實就算顏色可重複使用,作法亦相同:
以a,b二種顏色塗順時針1234四個位置,顏色可重覆時,平面環狀數:
(1)(2)(3)(4):2^4=16
(1234):2
(13)(24):2^2=4
(1432):2
所求即為(所有方法數)/(置換群個數)=(16+2+4+2)/4=6種

若求珠狀排列數:
(1)(2)(3)(4):2^4=16
(1234):2
(13)(24):2^2=4
(1432):2
(1)(3)(24):2^3=8
(2)(4)(13):2^3=8
(12)(34):2^2=4
(23)(14):2^2=4
所求即為(所有方法數)/(置換群個數)=(16+2+4+2+8+8+4+4)/8=6種

再來個例子:
求aabbcc環狀,珠狀排列數:
(1)(2)(3)(4)(5)(6):6!/(2!)(2!)(2!)=90
(123456):0
(135)(246):0
(14)(25)(36):3!=6
(153)(264):0
(165432):0

(1)(4)(26)(35):3*2!=6
(2)(5)(13)(46):3*2!=6
(3)(6)(24)(15):3*2!=6
(12)(36)(45):3!=6
(23)(14)(56):3!=6
(34)(25)(16):3!=6

所以環狀為(90+6)/6=16種;珠狀為(90+6+6*6)/12=11種

其實就算空間中的著色法都可以用這個方法解,僅需作出置換群即可,顏色可不可重複已經不是重點,只是空間中的立體圖形置換群個數較多,寫起來較繁雜一點,這個方法其實就是將每一種方法補成一樣多種後,再一次除以置換群總數,要體會的話其實不難的,你可以試著將所有算出的情形列出再觀察即可,詳細證明我就不寫囉!!

都都(ivan5chess) 於 2010-04-28 01:53 回覆：

嗯嗯看完我大概有回覆了一點記憶

也印象岡凌有跟我講過這個方法其實就是將每一種方法補成一樣多種後,再一次除以置換群總數

我想問一下....

置換群種類要怎麼看出來有那麼多種?

或者更精確的說...

怎麼知道不會更多或更少?


	陳

陳

2010/04/26 15:03

咦?熟悉的問題,好像我之前有跟同學講過說,有個公式解阿,是用置換群的方法解的,不過不曉得你同學有沒有跟你講阿,我要回去翻一下我的筆記本,我有寫下來,好像是叫作“波利亞定理”的樣子!!

都都(ivan5chess) 於 2010-04-26 20:50 回覆：

嗯嗯之前岡凌高三有跟我提過

但是可能是間接敘述的緣故,感覺很複雜XD所以現在也忘了...

他好像說這個方法可以用在任何排容有關的問題!

波利亞定理呀...嗯~英文是甚麼~?


		第頁／共 2 頁