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