排列組合3題

1. 正昇、得志、軒量、噴火承浩四人去吃飯，共有9樣菜，每人選3樣不同的菜，已知任兩人中都有選一樣共同的菜且恰只有一樣，求選法?

2. 正昇在2 × 7的方格中選取若干個格子塗成黑色(也可以全部不選)，使得任兩個黑色的格子都不共邊的方法有_______種。

3. 若正整數n小於1000且恰可以表示成5種j個接續正奇數之和，j≥1。試問這種n共有________個。

(以下解法若有錯誤，或另有更佳解法，敬請不吝提出)


1. 想法: 把所求分割成定義明確的互斥子集，常能簡化問題。


先考慮其中某三人 A，B，C，並將所求分割成 a. A∩B, A∩C, B∩C 皆相同; b. A∩B, A∩C, B∩C 皆相異 兩種情形。


a. A∩B, A∩C, B∩C 皆相同: 再分割成 D 是否選取了這個交集。


C(9,3)*3*C(6,2)*C(4,2)*(1*1 + 2³) =  204120


b. A∩B, A∩C, B∩C 皆相異: 再分割成 D 是否選取了某個交集(至多選取一個)。

C(9,3)*3*C(6,2)*2²*C(4,1)*[C(3,1)*1*C(3,1) + C(3,3)] = 604800


所求 = a. + b. = 808920

(以下解法若有錯誤，或另有更佳解法，敬請不吝提出)


2. 想法: 符合題意之 2 x n 的方格，可衍生自符合題意之 2 x (n-1) 的方格，反之亦然，這暗示了本題使用遞迴關係的可行性。


將合題意之 2 x (n-1) 的方格最右行分為 a. 二白 與 b. 一黑一白，它們各自可向右一行衍生出 a. 1 個"二白"與 2 個"一黑一白"，與 b. 1 個"二白"與 1 個"一黑一白" 之符合題意的 2 x n 方格。


若 W，G 分別表示 2 x (n-1) 方格最右行 "二白" 與 "一黑一白" 的個數，則與 2 x n 方格的遞迴關係為 (W, G) → (W+G, 2W+G)。


以下由 2 x 1 方格開始:


(1, 2) → (3, 4) → (7, 10) → (17, 24) → (41, 58) → (99, 140) → (239, 338)


所求 = 239 + 338 = 577


(就本題而言，分成: 恰 0 個黑格，恰 1 個黑格，...，恰 7 個黑格討論，亦不失為一可行的方法)

(以下解法若有錯誤，或另有更佳解法，敬請不吝提出)


想法: 利用等差級數和的性質，考慮正整數 n 的充要條件。


n = 等差級數和 = 中位數(M)*項數(N)，因此 1 種接續正奇數之和表示法，對應 1 種"兩個正整數的乘積(M*N)"，但反之不然，因為要符合:


1. 各項皆 >0，即 M > N-1。


2. 各項皆為奇數，即 M, N 奇偶性相同。


亦即，任取兩個奇偶性相同的正整數 M, N，即恰對應一個"接續正奇數之和表示法"。以下分為 a.  M, N 皆奇數，與 b. M, N 皆偶數 討論。


a.  M, N 皆奇數


以 n 的標準分解式思考: 考慮 n 可分為幾種"奇*奇"的情形與因數個數間的關係。因 n 恰可以表示成 5 種接續正奇數之和，即恰對應 5 組相異的 (M, N)，亦即 n 恰有 10 或 9 個因數。


再考慮 n (<1000) 的標準分解式中質因數的冪次為 (1,4) 或 (2,2)，得 n 有 5 個: 3⁴*5, 3⁴*7, 3⁴*11, 3²*5², 3²*7²


b.  M, N 皆偶數


以 n 的標準分解式思考: 考慮 n 可分為幾種"偶*偶"的情形與因數個數間的關係。


先各分 1 個 "2" 給 M 與 N，則剩下的部分必恰有 10 或 9 個因數 (方可構成 5 組"偶*偶")。再考慮 n/4 (<250) 的標準分解式中質因數的冪次為 (1,4) 或 (2,2)，得 n /4 有 10 個: 2⁴*3, 2⁴*5, 2⁴*7, 2⁴*11, 2⁴*13, 2*3⁴, 2²*3², 2²*5², 2²*7², 3²*5²。


所求 = a. + b. = 15 (個)

感謝cefepime老師的詳細解釋

三題都對啦!
好厲害!

cefepime 兄真神人也......

小弟提供前兩題的不同想法

(1) 這題可分以下三種情形討論
(i)4人共點6樣菜
易知每樣菜恰被2人所點
\(C_{6}^{9}\times 6!=60480\)

(ii)4人共點7樣菜
其中有1樣菜恰被3人所點，有3樣菜恰被2人所點，其餘3樣菜恰被1人所點
恰被3人所點的這樣菜，有\(C_{3}^{4}\)種被點情形
\(C_{7}^{9}\times C_{3}^{4}\times 7!=725760\)

(iii)4人共點9樣菜
其中有1樣菜恰被4人所共點，其餘8樣菜恰被4人所分點
\(C_{1}^{9}\times C_{2}^{8}\times C_{2}^{6}\times C_{2}^{4}\times C_{2}^{2}=22680\)

所求 = 60480 + 725760 + 22680 = 808920


(2) 用一階遞迴來做
設\({{a}_{n}}\)表示2列n行時，符合題意的方法數
則\({{a}_{n}}=2{{a}_{n-1}}+{{a}_{n-2}}\)
其中\({{a}_{1}}=3,{{a}_{2}}=7\)
所求為\({{a}_{7}}=577\)
亦可求出\({{a}_{n}}=\frac{1}{2}\left[ {{\left( 1+\sqrt{2} \right)}^{n+1}}+{{\left( 1-\sqrt{2} \right)}^{n+1}} \right]\)

[ 本帖最後由 thepiano 於 2014-12-28 11:03 PM 編輯 ]

piano老師也好厲害!
(1)每樣菜恰被2人所點
(2)有1樣菜恰被3人所點，有3樣菜恰被2人所點
(3)有1樣菜恰被4人所共點
恰都符合"任兩人恰都只有一道菜相同"，不易想到!