推 hua825 : 感謝，受益良多啊！！看來太多基礎沒有修好了ＸＤ 07/14 22:03
※ 引述《hua825 (e-hua)》之銘言：
: 請問一下版上各位高手
: 若今天有四個東西ＡＡＢＢ要進行環狀排列
: 要是直接手動用排得來做的話就是
: Ａ Ａ
: ＿ ＿
: Ａ ｜＿｜Ｂ Ｂ ｜＿｜ Ｂ
: Ｂ Ａ
: 應該就是這兩種情形
: 但是如果用算式的話列出來就怪怪的
: 4!
: -------
: 2!*2! 3
: --------------- = -----
: 4 2
: 算出來不一樣。所以想要請教一下各位，是哪邊出現了盲點呢，謝謝。
又到了 Burnside's theorem 上埸的時間囉~
設有 n_1 個 A_1,.., n_k 個 A_k 做環狀排列, n=n_1+..+n_k
現在我們的 group G 是 cyclic group C_n = <a>, 其中 a 為順時針轉1/n圈的 action
設 D=gcd(n_1,..,n_k), 對 0≦r≦n-1, 設 d=gcd(r,n)
則被 a^r 固定的排法必為「每隔 d 個位置要相同」
故被 a^r 固定的排法數為
d!
I_{(n/d)|D}*------------------------------
(n_1/(n/d))!*..*(n_k/(n/d))!
故在 C_n 的作用下的軌道數為
1 n-1 (gcd(r,n))!
--- Σ I_{(n/gcd(r,n))|D}*--------------------------------------------
n r=0 (n_1/(n/gcd(r,n)))!*..*(n_k/(n/gcd(r,n)))!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
對於本題
k=2, n_1=2, n_2=2, n=4, D=2
1 4! 2!
所求 = ---{I_{1|2}*(------)+I_{4|2}*(..)+I_{2|2}*(------)+I_{4|2}*(..)}
4 2!2! 1!1!
= 2
原po算法會有問題的原因如下：
一般而言, n 異物的環狀排列算法中 (1/n)(n!) 的 (1/n) 是因為
每一個排法在環狀排列下都會被重複計算 n 次, 故將排列數除以 n 即可得環排數
但不盡相異物的排法不一定都被重複計算 n 次
eg. AABB 在排列時有以下 6 種排法,
A A B B
A B B A B A A B => 在環排是同一種, 被重複計算 4 次
B B A A
B A
A A B B => 在環排是同一種, 被重複計算 2 次
B A
故環排數應為 4/4+2/2=2 而不是 4/4+2/4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
又用牛刀殺雞了...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.77.142
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1436881333.A.8C3.html
※ 編輯: XII (114.24.77.142), 07/14/2015 21:59:15