[中學] 106學測 排列組合 午餐問題

[ru04ul4 (拒絕)]

小明想要安排從星期一到星期五的午餐計畫
有四種選擇:牛肉麵 大滷麵 咖哩飯 排骨飯
這五天每天選一種
每種至少吃一次 不連續兩天吃麵
問有多少種不同的計畫

---

我的解答

設代號
麵N 牛肉麵A 大滷麵B
飯R 咖哩飯C 排骨飯D

五天不是3N2R就是2N3R

---

3N2R一定是NRNRN

N的部分 AAB ABA ABB BBA BAB BAA
R的部分 CD DC

3N2R 有6*2=12種組合

---

2N3R的情況

N的部分都是 AB BA

NRNRR

R的部分 CDC CCD DCD DDC (1)

NRRNR

同(1)

NRRRN

只能是 CDC或DCD

RNRNR

CCD CDC DCC DDC DCD CDD

RNRRN

同(1)

RRNRN

同(1)

所以是2*(4+4+2+6+4+4)=48

48+12=60

雖然答案是對的 但是實在太慢了
請問有沒有更簡單快速的解法呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.69.34.205
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1485833600.A.1AE.html
推 ckscks178   : 那是因為你窮舉... 用C啊...
推 aromaQ626   : 這題窮舉是最安全而且最快的以考生來講
→ aromaQ626   : 要用C也不是不行只是狀況限制太多討論的時間不會比
→ aromaQ626   : 一個一個數還快
推 aromaQ626   : 頂多也只是稍微簡化窮舉而已
→ ru04ul4     : 這題用C怎麼解@@？
推 mathfu      : 3N2R => C(2,1)*3!/2!=12
→ mathfu      : 3R2N => C(2,1)*[3!/2!*C(4,2)*2!-2!*C(3,2)*2!]
→ mathfu      : 3N2R 先選一種吃兩次的飯，不盡相異物排列後，麵插
→ mathfu      : 空格，3R2N 先選一種吃兩次的麵，一樣不盡相異物排
→ mathfu      : 列，但要減去連續兩天吃相同的飯
推 itsweb      : 後面ABCCD可以用 排容原理 AB不相鄰 CC不相鄰
→ itsweb      : 全部-AB相鄰-CC相鄰+AB相鄰且DD相鄰
推 gold97972000: 我的方法跟你一樣
推 tailent     : 題目少列：不能連續兩天吃相同餐點