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

[LeonYo (僕は美味しいです)]

排組大不同（一）　有Ｎ個不同物，放入Ｋ個不同箱，物全部放完


類型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: 用心！！首推！
推 ButterChang: 好懂!
推 AtDe: 話說至少放一的方法有時候也可以用分組分堆來做...
→ LeonYo: 樓上說的沒錯，例八就可以~
→ LeonYo: 其實是「理論上全部都可以」，只是有時簡單有時麻煩
→ LeonYo: 簡單時比排容簡單，麻煩時比排容麻煩，視情況而定
推 lovetwbbs: 未看先推
推 tomedc14: 推
※ 編輯: LeonYo (140.122.140.144), 08/21/2015 13:01:07
推 lp33506: 高調
推 a73108965: 幫高調 推
推 weegee1219: 推
推 feng0121: 推
推 ATHEM7: 高調
推 willy180439: 這單元就是搞不懂啊哭...
推 cold20922: 推
推 holishing: 重要推! (122的!?
推 lovehan: 推
推 lady012266: 至少就是只有2種算法: (1)扣除法(排容原理) (2)累加法
→ lady012266: (完全沒有，至少1.至少2...)
推 poposong: 超感謝
推 poposong: 超感謝
推 poposong: 超感謝
推 sweet2010126: 排列組合的秘方就靠你了大大
推 angellee0102: 推推