[問題] 不盡相異物的排列問題

看板Statistics作者 (阿比)時間5年前 (2020/04/06 03:58), 5年前編輯推噓1(1推 0噓 48→)
留言49則, 1人參與, 5年前最新討論串1/1
各位先進 小的不才 想請問基礎的排列問題 若要將n個不完全相異物進行排列 為何重複的種類的總和要用除的而不是減的？ 例如有3顆白球、2顆紅球及2顆黃球 我們將其排列的總和為7!/3!*2!*2! 但為什麼不是7!-3!*2!*2! 我知道用減的一定會少 答案一定不對 但這也僅止於強記的階段而已 我想知道原理是什麼 用除的跟用減的到底差在哪裡 請賜教 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.180.159 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Statistics/M.1586116727.A.D65.html
→
04/06 08:36, 5年前 , 1F
咦? 教本上沒說嗎. 例如 n 個球中有兩個球不可分吧. 比如
04/06 08:36, 1F
→
04/06 08:38, 5年前 , 2F
兩個 0 號球, 其餘標示 1～n-2 號. 如果兩個 0 號球可分的
04/06 08:38, 2F
→
04/06 08:40, 5年前 , 3F
話, 共 n! 種排列. 今兩個 0 號球不可分, 表示它們兩種排法
04/06 08:40, 3F
→
04/06 08:42, 5年前 , 4F
被視為一種. 因為兩個球的任一種排法對應其他球的排法是一
04/06 08:42, 4F
→
04/06 08:43, 5年前 , 5F
樣的, 因此直接 n! 除以 2! 就可以了. 3個球不可分, 以至於
04/06 08:43, 5F
→
04/06 08:45, 5年前 , 6F
多組不同的球不可分, 都相同想法可以類推.
04/06 08:45, 6F
→
04/06 08:46, 5年前 , 7F
至於用減法的情形是不一樣的, 那是:
04/06 08:46, 7F
→
04/06 08:47, 5年前 , 8F
(不限制時的排組數) - (不被允許的排組數)
04/06 08:47, 8F
→
04/06 08:49, 5年前 , 9F
例如有 "XX 與 YY 不可相鄰" 的條件. 先計算不限制相鄰的
04/06 08:49, 9F
→
04/06 08:51, 5年前 , 10F
方法數, 再扣掉違反條件(也就是XX與YY相鄰)的方法數.
04/06 08:51, 10F
→
04/06 08:52, 5年前 , 11F
請仔細想想這兩者的不同: 前者並沒有限制 "不允許...".
04/06 08:52, 11F
謝謝 我是搞不太懂為什麼有重複的組合像是你說的原本排列方法不可分的兩個0號球要扣掉的 時候是用除的
→
04/06 14:05, 5年前 , 12F
我們以 n=3 為例來說吧. 3個球 ox1,xo1,o1x,x1o,1ox,1xo
04/06 14:05, 12F
→
04/06 14:07, 5年前 , 13F
完全能分辨時就是3!=6種排列. 但 ox 和 xo 兩種視為一種,
04/06 14:07, 13F
→
04/06 14:09, 5年前 , 14F
就剩下 oo1, o1o, 1oo 3種. 這是 ox 和 xo 兩種排列視為
04/06 14:09, 14F
→
04/06 14:11, 5年前 , 15F
1種之故. 如果較大的 n, 也是一樣, ox 和 xo 被視為同一種,
04/06 14:11, 15F
→
04/06 14:14, 5年前 , 16F
總排列數就減半. 如果有3個球是不可分辨的, qox 3!=6 種排
04/06 14:14, 16F
→
04/06 14:16, 5年前 , 17F
列被視為一種, 總排列數就減為 1/6. 有h組不可分辨之物時
04/06 14:16, 17F
→
04/06 14:16, 5年前 , 18F
道理也是相同的.
04/06 14:16, 18F
推
04/06 14:21, 5年前 , 19F
也可這麼想: n個不盡相同物的排列中, 若其中 k 個相同物
04/06 14:21, 19F
→
04/06 14:23, 5年前 , 20F
若加上標記使成為可分辨, 是不是原來每一種排列可變化出 k!
04/06 14:23, 20F
→
04/06 14:24, 5年前 , 21F
種排刊? 如原來 oo1, o1o, 1oo. 如果兩個 o 可分辨, 成 xo,
04/06 14:24, 21F
→
04/06 14:25, 5年前 , 22F
則 oo1 變 xo1, ox1 兩種; o1o 變 x1o, o1x 兩種...
04/06 14:25, 22F
意思是說當n=3，有兩種球的時候，最直接的排法是3!=6，但因為ox及xo其實是同一種球 ，所以2!種排法就重複了要扣掉，到這裡我都懂，但就是3!/2!我不太能理解，因為一樣 所以要除掉這邊我過不太去，是因為2!種其實只有1種所以要均分掉嗎？
→
04/06 17:38, 5年前 , 23F
6種排列, 在 xo, ox 其實就是同一種的惰況, 就是說每一種
04/06 17:38, 23F
→
04/06 17:40, 5年前 , 24F
排列都重複了2次,xo1=ox1, x1o=o1x, 1xo=1ox. 所以 6除以 2
04/06 17:40, 24F
→
04/06 17:42, 5年前 , 25F
就消除了重複, 得到正確的排列數:3.
04/06 17:42, 25F
→
04/06 17:44, 5年前 , 26F
說 "均分掉" 有些怪, 其實只是消除重複.
04/06 17:44, 26F
→
04/06 17:46, 5年前 , 27F
再舉個 n=4, k=2 的情形吧. n!/k! = 4!/2! = 12, 表示 oo12
04/06 17:46, 27F
→
04/06 17:48, 5年前 , 28F
4個球其中2個不可分辨, 其排列法是 12種. 如果 oo 兩球可分
04/06 17:48, 28F
→
04/06 17:49, 5年前 , 29F
辨, xo12 共有 4!=24 種排列. 舉些例子, 如 x1o2,o1x2;
04/06 17:49, 29F
→
04/06 17:52, 5年前 , 30F
x21o,o21x; 1xo2,1ox2...這些排列我們故意兩兩一組放在一起
04/06 17:52, 30F
→
04/06 17:53, 5年前 , 31F
不難看出這每一組兩種排列在 oo 兩球實際上不可區分時是同
04/06 17:53, 31F
→
04/06 17:55, 5年前 , 32F
一種排列, 也就是每一種排列都被算了2次. 所以 oo12 的排列
04/06 17:55, 32F
→
04/06 17:57, 5年前 , 33F
數必須從 4! 中消除這種重複. 因為每一種排列都被算了2次,
04/06 17:57, 33F
→
04/06 17:58, 5年前 , 34F
所以 oo12 的排列數就是 4!/2! (或 4!/(2!1!1!).)
04/06 17:58, 34F
→
04/06 18:00, 5年前 , 35F
再如 n=4, k=3. ooo1 的排列是 4!/3! = 4 種, 即 ooo1,oo1o
04/06 18:00, 35F
→
04/06 18:02, 5年前 , 36F
o1oo, 1ooo. 但如 3個 o 可區分, ooo1 這種排列對應了6種.
04/06 18:02, 36F
→
04/06 18:06, 5年前 , 37F
重新標記ooo為zxo,則 ooo1→zxo1,zox1,xzo1,ozx1,xoz1,oxz1
04/06 18:06, 37F
→
04/06 18:08, 5年前 , 38F
ooo1的每一種排列在ooo不再不可區分時都變成 3!=6 種排列,
04/06 18:08, 38F
→
04/06 18:10, 5年前 , 39F
就這樣我們得到熟知的4相異物 4!=24 種排列. 可是 ooo 其
04/06 18:10, 39F
→
04/06 18:11, 5年前 , 40F
實不可分, 所以 ooo1 只有 4!/3! 種排列.
04/06 18:11, 40F
感謝你！到這邊我懂了，剩下的我有在math版re文底下推文回覆你了 ※ 編輯: nest0380 (114.36.180.159 臺灣), 04/06/2020 20:02:22
→
04/06 21:09, 5年前 , 41F
假設不盡相同物是: 黑球3,白球2. 那麼白球可區分而黑球不可
04/06 21:09, 41F
→
04/06 21:10, 5年前 , 42F
區分時, 依只有一種多個不可區分物的排列數是 5!/3!=20.
04/06 21:10, 42F
→
04/06 21:12, 5年前 , 43F
但如白球也不可分, 同樣的在前面假設白球可分時等於同樣重
04/06 21:12, 43F
→
04/06 21:14, 5年前 , 44F
複計算了排列數. 例如 BBWBW 在假設白球可分(例如標記12)時
04/06 21:14, 44F
→
04/06 21:17, 5年前 , 45F
被算予2次: BB1B2 及 BB2B1. 又如 BWBBW 也被算2次:B1BB2及
04/06 21:17, 45F
→
04/06 21:18, 5年前 , 46F
B2BB1. 如此, 3B2W 的排列在假設2白球可區分時都被算了2次.
04/06 21:18, 46F
→
04/06 21:21, 5年前 , 47F
所以 BBBWW的排列數 = BBB12的排列數再除以2! = 5!/(3!2!)
04/06 21:21, 47F
→
04/06 21:24, 5年前 , 48F
以此類推, n件不盡相同物, 其中有3種物各有 r件,s件,t件,
04/06 21:24, 48F
→
04/06 21:26, 5年前 , 49F
則排列數是 n!/(r!s!t!) 此公式可推至更多種各有多件的情形
04/06 21:26, 49F
‣ 更多 nest0380 的文章
文章代碼(AID): #1UYZXtrb (Statistics)