由於多數同學對排列組合感到困擾,我想試著寫些詳解,
讓同學抓到一些解決排列組合問題的想法與脈絡,隨手選
了 106學測單選7 來寫詳解,這題即使是高分群(前33%)
也只有 40%的答對率,從選項分析來看錯答選項幾乎平均
分配,感覺就像是隨機猜答似的,因此這題對整體考生而
言絕對不算是簡單的題目。以下附上題目及我寫的詳解,
想知道這樣的寫法對於不擅長排列組合的同學有無幫助,
歡迎給予各種指教,謝謝。
【106學測單選7】
小明想要安排從星期一到星期五共五天的午餐計畫。他的
餐點共有四種選擇:牛肉麵、大滷麵、咖哩飯及排骨飯。
小明想要依據下列兩原則來安排他的午餐:
(甲)每天只選一種餐點但這五天中每一種餐點至少各點一次
(乙)連續兩天的餐點不能重複且不連續兩天吃麵食
根據上述原則,小明這五天共有幾種不同的午餐計畫?
(1) 52 (2) 60 (3) 68 (4) 76 (5) 84
【解答】
這是星期一到星期五的計畫,我們可以在紙上畫個簡表
┌────────────────────┐
│ 一 二 三 四 五 │
│ │
讀完(甲)條件,我們要知道兩件事情:
第一、有五個「不同」的日子,而且每一個不同的日子「
要剛好選一樣」餐點,所以這是排列問題。
第二、因為只有四種餐點,而且每種至少要點一次,所以
必然有一種餐點會重複,此時我們知道會有四種可
能的分類。
讀完(乙)條件,要知道這題目有兩個「反面限制」:
第一、連續兩天餐點不能重複,用排列的角度來看,其實
就是「相同物不能相鄰」。
第二、不連續兩天吃麵食,用排列的角度來看,也是「某
些物不能相鄰」的條件。
一般來說,如果只有「一組」不相鄰的反面限制,可以用
插入法解決就好;如果有「兩組以上」不相鄰反面限制,
用「取捨原理」處理會好一些。但「取捨原理」對大部分
的同學來說是不容易理解也不容易想到的方法,以下我們
先用「窮舉討論」的方法來處理這兩個反面限制,再使用
取捨原理處理一次。
我們先從條件(甲)開始討論起,有四種重複的可能:
牛牛大咖排、牛大大咖排、牛大咖咖排、牛大咖排排。
因為中文書寫較為麻煩,考試時同學應該適時地轉化為符
號表示,以下我們用 aabxy, abbxy, abxxy, abxyy 作為
討論。為何要用 ab 和 xy 而不用 abcd 呢?同學在看完
條件(乙)後,要能夠知道題目對於「麵」和「飯」的處
理方式是不一樣的,因此我們用 ab 和 xy 差異較大的符
號來作分類,較符合直覺的感受,比起排列 abcd 更能夠
直覺地感受到題目對飯與麵的差別對待。
先排列 aabxy,因為題目要求麵不能重複,aab 勢必要完
全分開,因為只有 5 個位置,所以排列方式必然為
a_a_b
的形式,其中 aab 的排列可能為 aab、aba、baa 有 3 種
排法,而空格可以填 xy 和 yx 有 2 種排法,所以共有 6
種排法。再排 abbxy,道理和 aabxy 相同,所以也有 6 種排法。
接著排 abxxy,由題意可知 ab 不能相鄰 xx 也不能相鄰,
看起來是很麻煩的條件,很多同學不知如何是好,可能就對
著題目發呆或跳過了,事實上,同學一定要「動筆寫出來試
試看」才有機會解出題目,我們就先把 ab 不相鄰的所有可
能列出來吧:
a _ b _ _
a _ _ b _
a _ _ _ b
_ a _ b _
_ a _ _ b
_ _ a _ b
因為只有 5 個位置,所以就算全部列出來,也不是很困難的
事情。但要注意,以上列的是 a 前 b 後的情形,還有 b 前
a 後的情形別忘了。列出來後,我們插入 xxy,只要注意
xx 不相鄰就好了。因為剩下來的工作已經很少,我們只要
依序看著列出來的 6 種情形,插入 xxy 各有幾種排列方式
就好,沒有必要再把 xxy 的所有可能寫出來。
a _ b _ _ 插入 xxy 且 xx 不相鄰有 2 種方法;
a _ _ b _ 插入 xxy 且 xx 不相鄰有 2 種方法;
a _ _ _ b 插入 xxy 且 xx 不相鄰有 1 種方法;
_ a _ b _ 插入 xxy 且 xx 不相鄰有 3 種方法;
_ a _ _ b 插入 xxy 且 xx 不相鄰有 2 種方法;
_ _ a _ b 插入 xxy 且 xx 不相鄰有 2 種方法。
由以上討論可知共有 12 種方法,但別忘了,還有 b 前 a
後的情形,所以 abxxy 符合題意的排列一共有 24 種。同
樣的道理, abxyy 也會有 24 種。綜合以上討論,我們就
有 6+6+24+24=60 種不同的方法。
以上的方法是「根據題目的條件,一步一步慢慢達成題目
的要求」,因此我們分了好幾個步驟來處理,其實這才是
排列組合最重要的精神。大部分的題目,只要「分成適當
的步驟」就能解決了,背了很多題型和公式卻不知如何運
用,反而拿不到分數。
排列 abxxy 時,有兩個反面限制,ab 不相鄰且 xx 不相
鄰,能力較強的同學可以考慮使用取捨原理,也就是:
(ab 不相鄰且 xx 不相鄰)的方法數
= 所有的方法數 -(ab 相鄰)的方法數
-(xx 相鄰)的方法數
+(ab 相鄰且 xy 相鄰)的方法數
再分別把上式的各種方法數求出來就好。
所有的方法數 = 5!/2! = 60
即abxxy 不盡相異物的排列
ab 相鄰的方法數 = (4!/2!)2!= 24
即 (ab)xxy 排列:先外部排 ()xxy 再內部排 (ab)
xx 相鄰的方法數 = 4!= 24
即 ab(xx)y 排列:先外部排 ab()y 再內部排 (xx)
ab 相鄰且 xx 相鄰的方法數 = 3!2! = 12
即 (ab)[xx]y 排列:先外部排 ()[]y 再內部排 (ab) 和 [xx]
因此 abxxy 共有 60 - 24 -24 +12 = 24 種排列方法