[情報] 排組大不同（一）

看板SENIORHIGH作者LeonYo (僕は美味しいです)時間8年前 (2015/08/21 02:09)推噓20(20推 0噓 4→)

留言24則, 19人參與討論串1/1

排組大不同（一）　有Ｎ個不同物，放入Ｋ個不同箱，物全部放完類型1. 任意分 (常見的基本題型) 選定一物，只能放一箱選定一箱，可以放多物 →可視為以物為自變數（在定義域內）　　　　以箱為應變數（在對應域內）的一對多函數關係（對應關係）　只要「對應關係不同」即視為結果不同（排組要算的是有幾種不同的結果）例一：有 5 個不同物 a, b, c, d, e 　　　要全部任意放入 3 個不同的箱子 x, y, z 物 a b c d e 箱 x y z y x 　　　箱 x y z y z 對應關係不同(e→x 與 e→z 不同) 即為二種不同的排列方式. Ans: 3^5 例二：有 3 個不同物，全部任意放入 5 個不同箱. Ans: 5^3 例三：有 3 個不同物，全部任意放入 3 個不同箱. Ans: 3^3 例四：有 n 個不同物，全部任意放入 k 個不同箱. Ans: k^n 結論是，這種函數對應關係，與 n, k 多寡無關類型2. 每箱最多 1 物 (極好算的無聊變化題) 選定一物，只能放一箱選定一箱，最多放一物 →只要物不同，必放不同箱 →可視為以物為自變數，以箱為應變數的一對一函數　當物數同於箱數時，為一對一且 onto 函數，有反函數（故可以箱選物）　當物數少於箱數時，為一對一但非onto函數，無反函數（只能以物選箱）例五：有 3 個不同物 a, b, c 要全部放入 5 個不同的箱子 x, y, z, u, v 且每箱至多一物 Ans: 5*4*3 例六：有 3 個不同物 a, b, c 要全部放入 3 個不同的箱子 x, y, z 且每箱至多一物 Ans: 3*2*1 例七：有 n 個不同物，要全部放入 k 個不同的箱子 (n≦k) 且每箱至多一物 Ans: k*(k-1)*...*(k-n+1) = P(k,n) 類型3. 每箱最少 1 物 (討人厭的麻煩排容題型) 這裡基本上還是函數對應關係，只是要利用排容扣掉不合的情形要算排容之前，要先理解「排列組合」和「集合」的關係以及「聯集內元素個數」如何計算的問題例八：有 5 個不同物 a, b, c, d, e 　　　要全部放入 3 個不同的箱子 x, y, z 且每箱最少 1 物 [Sol]:首先宇集內的元素，就是各種不同的放法（即任意分）　　　如 U = {(x, x, x, x, x), [就是a, b, c, d, e都放x] (y, x, z, y, x), [就是a→y,b→x,c→z,d→y,e→x] ...} 所以 n(U)= 3^5 = 243 　　　但這裡面有很多不合的排法，我們必須予以扣除　　　例如把 x 箱子裡沒東西的排列方法放到 X' 集合裡 X'= {(y, y, y, y, y), (y, z, y, y, z)...} y 沒東西的 Y'= {(x, x, z, z, x), (z, z, z, z, z)...} z 沒東西的 Z'= {(y, x, y, x, y), (x, x, x, x, x)...} 只要符合以上任一項，我們都必須予以扣除因此我們要扣的事實上是Union(X', Y', Z') 排容原理(取捨原理)，就是扣掉這個我們不要的聯集聯集的計算不另說明　　　但要提醒的是，常有同學去背排容原理的係數: C(n,1), C(n,2),... 　這個係數可用的前提是同階的交集元素個數相同　　　如果你不知道我在說什麼，要嘛快去搞清楚，要嘛不要亂背東西　　　回到原題 n(X'∪Y'∪Z') = n(X') + n(Y') + n(Z') -n(X'∩Y') -n(X'∩Z') -n(Y'∩Z') +n(X'∩Y'∩Z') = C(3,1)*(2^5) - C(3,2)*(1^5) + C(3,3)*(0^5) 所求 = n(U) - n(X'∪Y'∪Z') = C(3,0)*(3^5) - C(3,1)*(2^5) + C(3,2)*(1^5) - C(3,3)*(0^5) = 243 - 96 + 3 - 0 = 150 (本來有計算錯orz) [Wrong Sol] 　　　常見同學這麼做：　　　要每箱各一個？簡單嘛，我就先各給一個呀～把 a, b, c 一對一丟到 x, y, z 去， 3! 種 get! 再把 d, e 任意分配到 x, y, z 去， 3^2種 get! 　　　一共是3!*(3^2)=6*9=54 　　　這個錯誤少算了很多情形，例如 (x, x, x, y, z) 不會被算到　　　因為一開始就指定 a, b, c 要給 x, y, z 但這根本不必然。　　　　更常見程度稍好的同學這麼做：　　　好吧，那我就讓 x, y, z 任選總行吧， 5*4*3 = 120 get! 你看我的 (x→a, y→d, z→e)總可以數到你剛舉的例子吧! 那還剩下兩個東西{b,c}還沒放，就亂放嘍，3^2=9 get! 所以一共是 120*9=1080 　　　過猶不及！剛少算現在多算了！ (x, y, z) (d, e) (a, b, c) (x, x) 這是剛剛算法裡的某一種結果。 x, y, z 先選了a, b, c, 然後剩下的d, e 任選選到了 x, x (x, y, z) (a, d) (e, b, c) (x, x) 這是剛剛算法裡的某一種結果。　　　　　　　　　　　 x, y, z 先選了e, b, c 然後剩下的a, d 任選選到了 x, x @@" 不同的過程選到了相同的結果！　　　所以「過程」(即樹狀圖的枝數)與「結果」(所求)沒有一一對應!! 第二種錯誤有個重要特徵，就是「同一個箱子內的數個物品被分段放入」只要發生這種事情，我能說有99%都是錯的算法感謝AtDe大補充分組分堆作法 [Sol]:先依數量分布作分類，再依物品分配(內容)作排組，最後計算總排列數本題數量分布只有二類： x y z I 1 1 3 II 1 2 2 I x 先選 1 個，得 C(5,1) = 5 y 再選 1 個，得 C(4,1) = 4 z 拿剩下的全部，只有 1 種共有 5*4 = 20 因為數量分布 (1,1,3), (1,3,1), (3,1,1) 的取法相同故共有 20*3 = 60 種 (會不會有人誤認為是 20*(3!) 種呢? 想一下，要小心哦!) II x 先選 1 個，得 C(5,1) = 5 y 再選 2 個，得 C(4,2) = 6 z 拿剩下的全部，只有 1 種共有 5*4 = 30 因為數量分布 (1,2,2), (2,1,2), (2,2,1) 的取法相同故共有 30*3 = 90 種，故共有 150 種 (會不會有人誤認為是 30*(3!) 種呢? 想一下，要小心哦!) 另外，如果數量分布是 (1,2,3) 這種類型的，一共會有 3! 種哦當然，同樣講分組分堆，有人的算法是這樣的以 (1,1,2) 為例 {[C(5,1)*C(4,1)*C(2,2)]/(2!)}*3! 這是常看到的先分三堆，再分配給三個人的想法再這裡要注意的是「數量相同的分堆才要去除其有序性」要再多講的是，「乘法原理本身就隱含順序」以上是ｎ個不同物，全放入ｋ個不同箱的題型基本上就是函數的對應關係，在某些子分類下有討厭的排容原理，但沒有比排容原理更好處理的方式了orz ← 這句話要修正一下，在數量少時，用分組分堆作應該較簡單在數量多時，才用排容吧~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.4.201 ※ 文章網址: https://www.ptt.cc/bbs/SENIORHIGH/M.1440094152.A.57E.html

推

sk90040

08/21 07:19, , 1^F

08/21 07:19, 1^F

推

ButterChang

08/21 07:43, , 2^F

08/21 07:43, 2^F

推

AtDe

08/21 08:02, , 3^F

08/21 08:02, 3^F