[106學測，排列組合] 小明午餐計畫安排：牛肉麵、大滷麵、咖哩飯及排骨飯

 ==問題==

小明想要安排從星期一到星期五共五天的午餐計畫。他的餐點共有四種選擇：牛肉麵、大滷麵、咖哩飯及排骨飯。小明想要依據下列兩原則來安排他的午餐：

（甲）每天只選一種餐點但這五天中每一種餐點至少各點一次；

（乙）連續兩天的餐點不能重複且不連續兩天吃麵食。

根據上述原則，小明這五天共有幾種不同的午餐計畫？

(１)52    (2)60    (3)68    (4)76    (5)84

（出處：106，學測數學）

==答案==

(2)

==解析==

首先，因為餐點只有4種，而每天都只能吃1種，然後又每種都至少必須點1次，這表示必然有其中一種餐點選了2次（而其他餐點都被各選1次）。

為了討論方便，我們將4種餐點分別記為$N_1, N_2, R_1, R_2$（麵：Noodle；飯：Rice）。

按照前文所述，當我們只先關心該週餐點構成，先不討論吃的順序，那就有以下4種情況：

（1）$N_1$重複：$N_1, N_1, N_2, R_1, R_2$

（2）$N_2$重複：$N_1, N_2, N_2, R_1, R_2$

（3）$R_1$重複：$N_1, N_2, R_1, R_1, R_2$

（4）$R_2$重複：$N_1, N_2, R_1, R_2, R_2$

接著我們來處理排列的順序。

根據條件（乙）「連續兩天的餐點不能重複且不連續兩天吃麵食」，那麼以上的4種情況中，前兩種（麵重複）比較容易處理，我們可以用兩個$R$去把三個$N$給隔開，形如

$$N_\square R_\square N_\square R_\square N_\square$$

（注意現在已經開始考慮順序了！）以情況（1）來說，兩個$R$的下標只能不重複地填入1與2，然後三個$N$的下標就是填入兩個1與一個2，因此方法數為

$$2! \times \frac{3!}{2!1!} = 2 \times 3 = 6.$$

情況（2）討論的方式也相同，只不過在填入三個$N$的下標時改為填入一個1與兩個2。因此方法數同樣也是

$$2! \times \frac{3!}{1!2!} = 2 \times 3 = 6.$$

然後是情況（3）與（4）了。

同樣根據條件（乙），對於情況（3），必須①$N_1, N_2$不相鄰、②$R_1, R_1$不相鄰，這種限制位置的排列問題，依照過去學習經驗，我們應該採用排容原理。設事件$A=\{N_1, N_2\text{不相鄰}\}$、事件$B = \{ R_1, R_1不相鄰 \}$，於是

$$A'=\{N_1, N_2\text{相鄰}\}, B' = \{ R_1, R_1相鄰 \}.$$

注意無論是$n(A'), n(B')$還是$n(A' \cap B')$都很容易計算！使用排容原理與De Morgan定律，我們有

$$\begin{align*}  n(A \cap B) &= n[(A' \cup B')'] \\ &=n(U) - n(A' \cup B') \\ &=\frac{5!}{2!} - [n(A') + n(B') - n(A' \cap B')] \\ &= 60 - \left[\frac{4!}{2!}\times 2! + 4! - 3!\times 2!\right] \\ &= 60 -[24 + 24 - 12] \\ &= 24. \end{align*}$$

情況（4）的討論基本上與情況（3）相仿，只是要把本來的事件$B = \{ R_1, R_1不相鄰 \}$換成事件$C = \{ R_2, R_2不相鄰 \}$，然後計算的方式與數字都會完全相同，因此方法數同樣也是24。

綜上所述，小明安排午餐的方法一共是$6 + 6 + 24 + 24 = 60$種，選(2)。

（解答終了）