→ koala0716:抱歉> < 我沒有說清楚 題目是 阿不可以跟美相鄰 對不起 05/07 00:31
: 2.科目：排列組合
: 3.章節：直線排列 不能相鄰
: 4.題目：3個美國人 2個阿拉伯人 2個台灣人 1個法國人
: 5.想法：我從正面想跟反面想都覺得很麻煩 分類討論很久
: 不知道高手有沒有好想法 可用H嗎?
: thanks^^
先排後面五個人 阿阿台台法
1.阿阿相鄰 台台也相鄰 3!=6
則插入美時 必插入阿阿與台台中間,剩下一個美還有四個間隔可選=> 6*4=24
2.阿阿相鄰 台台不相鄰 2!*C(3,2)=6
則插入美時 必插入阿阿中間,剩下兩個美還有五個間隔可選=> 6*C(5,2)=60
3.台台相鄰 阿阿不相鄰 =>同2. 有60種
4.阿阿不相鄰 台台也不相鄰=>任意排列減上面三種 5!/2!2!-6-6-6=12
則插入美時 五個間隔選三個=> 12*C(6,3)=240
共有24+60+60+240=384
最後乘上人的排列3!2!2!=>9216(剛剛上面只排國籍而已)
--
用另外一種方式討論不知道對不對...
先把三個美與一個法排列...
共有四種...
但是可以看成兩種...
(1)三個美相連...
(2)或是中間有一個法...
再來是把兩阿兩日放進去...
分做四+1種情形...
一是四個全分開...
二是只有一組阿日相鄰...
三是兩組阿日...
四是阿日互夾Ex:阿日阿+日
+1是阿日阿日互換(但只有第2種OK...)
所以方法數變成
(1)2*{C(3,1)*4!/(2*2)+C(3,1)*3!*2+2!*2!+2*2!}
(2)2*{C(4,3)*4!/(2!*2!)+C(4,2)*3!*2!+C(4,1)*2!*2!+2*C(4,1)*2!+2}
排完國籍再排人*3!*2!*2!
(1)=124
(2)=240
Total=384*24=9216 #
第三種做法是直接用錯排or排容原理
全-一組相鄰+兩組相鄰-三組皆相鄰...
最麻煩的地方莫過於有三美...
討論如下...
(8!/2!*3!*2!)-C(2,1)*7!/(2!*3!)-C(6,1)*6!/(2!*2!)+
6!/3!+C(2,1)*(5!/2!)*C(5,1)-C(4,1)*4!
=8*7*6*5-7*6*5*4-6*6*5*3*2+6*5*4+5*5*4*3*2-4*4*3*2
=30*{56-28-36+4+20}-96
=30*16-96
=384
384*24=9216#
在第三種方法裡的算法是將相鄰時兩美先綁一起...
另一個等排完再進去選位置...
那因為如果在綁一起的兩美左右的話是等價的...
看上去都是美美美...
所以只算一種放法...
以上小弟淺見...
如有不周延或表達不仔細的地方...
歡迎大家討論...
※ 編輯: donflying 來自: 59.115.229.95 (05/06 16:48)