推 recipro : 大推! 12/21 21:16
推 coolbetter33: 推 12/21 22:49
推 Tiderus : 看不懂XD 12/21 23:16
推 altecgp125 : 這定理好難@@ 推白話文 12/23 16:16
推 cutekid : 大推(Y) 01/06 14:00
※ 引述《a016258 (憨)》之銘言：
: ※ 引述《ballballking (蛋蛋王)》之銘言：
: : aabbccdd 環狀排列有幾種排法呢
: : 我的想法是7!/(2!2!2!2!)=315
: : 但是解答卻是318
: : 請問我這樣算有露算或哪裡有問題嗎
: : 一直想不通
: : 感謝!
: 不盡相異物的環狀排列
: http://www.sec.ntnu.edu.tw/Monthly/95%28286-295%29/292-pdf/03.pdf
: (2,2,2,2) = 2
: 2 的正因數 1 , 2
: w_1 = 1
: |S_1| = 8!/(2!)^4 - (8/2)! /[(2/2)!]^4 = 2520 - 24 = 2496
: w_2 = 2
: |S_2|= 4! / [1!]^4 = 24
: 排列數 = 2496 / 8 + 2*24/8 = 318
Burnside's Lemma
X: finite set
G: finite group act on X
X_g = {x in X: gx=x} (the set of elements in X fixed by g)
1
=> #{orbits of X under G} = |X/G| = -----Σ_{g in G} |X_g|
|G|
(以下白話文)
X: 不可亂動的一般排法
G: 可以玩弄 X 的方法 (所形成的群)
=> 在 G 的玩弄下, X 的排法數
1
= -------------- Σ_{g:玩弄方法} {X 中在 g 玩弄下會固定不變的排法數}
玩弄方法總數
ps. G 需滿足: (即"群"的定義)
1. 不玩弄也是玩弄的一種 (identity in G)
2. 連續兩次玩弄也是一種玩弄 (g,h in G => gh in G)
3. 可以玩弄過來,就可以玩弄回去 (g in G => g^-1 in G)
e.g. 1,2,3,..,n 環排的方法(無聊的例子)
sol. X = {1,2,..,n 在圓上 n 個等分點的排列(不可轉)}
G = {1,a,a^2,..,a^{n-1}},
a = 逆時針轉1/n圈, |G| = n
|X_{1}| = n! (你不玩弄它,不管初始怎麼排,它都不變)
|X_{a^k}| = 0, k = 1,..,n-1 (若有轉k/n圈,則必與初始排法不同)
1
=> 有 ---{n!}=(n-1)! 種
n
e.g. 1,1,2,2,..,n,n (n>1) 環排的方法
sol. X = {1,1,2,2,..,n,n 在圓上 2n 個等分點的排列(不可轉)}
G = {1,a,a^2,..,a^{2n-1}},
a = 逆時針轉1/(2n)圈, |G| = 2n
|X_{1}| = (2n)!/2^n (你不玩弄它,不管初始怎麼排,它都不變)
|X_{a^k}| = 0, k = 1,..,2n-1 且 k≠n (必與初始排法不同)
|X_{a^n}| = n! (有 n! 種排法會被轉半圈固定, 即 xyz..xyz..)
1
=> 有 ----{(2n)!/2^n + n!} 種
2n
e.g. 1,1,2,2,..,n,n (n>1) 珠排的方法
sol. X = {1,1,2,2,..,n,n 在圓上 2n 等分點的排列(不可轉或翻)}
G = {1,a,a^2,..,a^{2n-1},b,ba,..,ba^{2n-1}},
a = 逆時針轉1/(2n)圈, b = 沿一特定的方向翻面, |G|=4n
|X_{1}| = (2n)!/2^n (你不戲弄它,不管初始怎麼排,它都不變)
|X_{a^k}| = 0, k = 1,..,2n-1 且 k≠n (轉 k/n 圈必與初始排法不同)
|X_{a^n}| = n! (有 n! 種排法會被轉半圈固定, 即 xyz..xyz..)
|X_{ba^k}| = n!, k=0,...,2n-1 (有 n! 種排法會被翻面固定,即..zyx|xyz..)
1
=> 有 ----{(2n)!/2^n + n! +(2n)n!} 種
4n
e.g. 用 n 色塗正六面體(可翻轉)的方法數
sol. X = n 色塗正六面體的方法, |X| = n^6
G = 正六面體的轉法, |G| = 8*3 = 24
不動(1個): |X_g| = n^6
以相對面的中心連線為軸轉 90, 270 度(6個): |X_g| = n^3
(不與軸相交的 4 面同色)
以相對面的中心連線為軸轉 180 度(3個): |X_g| = n^4
(不與軸相交的 4 面, 相對的面同色)
以不同面的平行稜中點連線為軸轉 180 度(6個): |X_g| = n^3
以體對角線為軸轉 120, 240 度(8個): |X_g| = n^2
1
=> 有 ---- (n^6 + 6*n^3 + 3*n^4 + 6*n^3 + 8*n^2) 種
24
e.g. 60 異球放入 3 同色箱的方法數
sol. 先將 3 箱有編號
X = 所有放法, |X| = 3^60
G = 玩弄編號的方法, |G| = 3!
|X_{不玩弄}| = 3^60
|X_{i,j互換}| = 1 (i,j二箱均不放) (3個)
|X_{1,2,3輪換}| = 0 (2個)
1
=> 有 --- (3^60+3*1) 種
6
e.g. 60 同球放入 3 同色箱的方法數
sol. 先將 3 箱有編號
X = 所有放法, |X| = H(3,60)
G = 玩弄編號的方法, |G| = 3!
|X_{不玩弄}| = H(3,60)
|X_{i,j互換}| = 31 (i,j二箱放同球數) (3個)
|X_{1,2,3輪換}| = 1 (三箱放同球數) (2個)
1
=> 有 --- (H(3,60)+3*31+2*1) 種
6
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.71.95
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1419101606.A.4DB.html