Re: [問題]神奇的200

> ==>發信人: tester@Evergreen (try or test), 信區: programming
> > ==>發信人: [e-mail] (), 信區: programming
> > ※ 引述《[e-mail] (try or test)》之銘言：
> > > 如果只是問有幾種串法, 把排列組合的公式套進去, 還是很快可以算出來.
> >     請問一下，排列組合的公式怎麼套啊？
> 三色各一球 c=3 n=1
> c*(c-1)*(c*n-2)
> 三色各兩球 c=3 n=2
> c*(c-1)*(c*(n-1)-2)*[(c-1)*(c-1)*(c*n-5)+1]
> 加 1 是因為 ABC-ABC 可以在第三, 四 位置對調多出一種 ABA-CBC
> =======
abacbc  如果是排成環, 還是會變成 acbcab , 因為原題是三色環, 相
鄰不同色. 對環的解法之一是先訂住一個色球, 想像先拆成一排, 又因
為三色數量各為 n = 1/3 總數, 把三個位置排一組就可以簡化數量限
制問題.
先訂三色為 ABC , 假設固定從 A 球拆成直排

n = 1
ABC , ACB 只有  2 種 (這要看平面環的方向是否視為相同 ?)

n = 2
固定 第一位置為 A
(1*2*1) * (2*2*1) = 8
但最後一位為 A 的應排除
(1*2*1) * ( 2*2*1 -1)
但 ABC-ACB 如果是環, 跟 ACB-ABC 是相同的
故 2*3 -1 = 5 

n=3
三個一組拆分, 每組就只有 6 種
1 = ABC
2 = ACB
3 = BAC
4 = BCA
5 = CAB
6 = CBA

固定第一位置為 A , 第一組有 2 種 , 第二組依第一組的尾位顏色而定
只有
1-{1,2,3,4}
2-{1,2,5,6}
共 (1*2*1)*(2*2*1) = 8 種
第三組受限其首尾的顏色, 最後一個不能是 A, 也就是 4,6 被排除
1-1-{1,2,3}
1-2-{1,2,5}
1-3-{1,2,3}
1-4-{3,5}
2-1-{1,2,3}
2-2-{1,2,5}
2-5-{1,2,3}
2-6-{3,5}
共 (1*2*1)*[(2*2*1)*(2*2*1-1) - 1) = 22 種

再排除 (1-2-1 , 1-1-2, 2-1-1) 
(1-3-1 , 1-1-3)
(122, 221, 212)
(125, 251)
(132, 213)
循環相同這類的, 可扣除 7 種
22 - 7 = 15 種

n=4
固定第一位置為 A, 前三組排列共為
(1*2*1)*(2*2*1)*(2*2*1) = 32 種
加入第四組, 再考慮最後一組的首尾排除與可能的循環.
=======
這還是窮舉扣除, 應有高人可以給通式.

--
 ◎ Origin: 中央松濤站□bbs.csie.ncu.edu.tw  From: 140.115.6.234