作者cornerstone (cornerstone)
看板Math
標題[中學] 排組的問題
時間Thu Oct 13 21:32:14 2022
不好意思，又想請教大家一題數學問題，
有附上我的想法，但需要板上朋友們幫忙。
有m個（m大於等於2）不同的球，以及n個(n大於等於2)不同的球袋，
把球全部分裝到球袋裡後，
有多少種情形是「有至少兩個球被分到同一個球袋裡」？
（假設題目是m個相同的球分到n個不同的球袋，就可以用重複組合H的公式，
可是這題是不同的球和不同的球袋，還能有公式嗎？）
我目前是用具體的數字來想，然後想到這個題目可能要分兩種情況來想，
第一種是球比球袋多時:
假設有三個不同的球和兩個不同的球袋，這時有(3,0)和(2,1)兩種情況
因為球和球袋都不同，所以(3,0)時有兩種分法
(2,1)時有(C3取2)*(C2取1)＝6種分法，所以總共就是8種分法
另一種想法是，因為不管怎麼分，都一定會有兩顆球被裝到同一個袋子裡，
所以也就是全部的分法：2^3 (每個球都有兩個球袋的選擇)
第二種是球比球袋少時：
假設兩個不同的球和三個不同的球袋：
因為要算至少有兩顆球被分到同個球袋裡，
所以就只能從三個球袋裡選一個裝兩顆球
(C3取1）= 3 種分法
但因為數字太小，所以又增加一點變成
六顆不同的球分到四個不同的球袋裡，這時也因為球比較多，
不管怎麼分都會有袋子裝至少兩顆球
也就是全部隨便沒有限制的分法：4^6
但假設四顆不同的球要分到六個不同的袋子裡，
而且最少有兩個球分到同一個袋子裡的情況就有很多種：
(這裡開始就有點不太確定了...)
我是列出各種狀況：
(2, 1, 1, 0, 0, 0) => 其中一個袋子裝兩顆，另外兩個袋子各裝一顆
但因為球跟袋子都不一樣，所以:
(C6取1)*(C4取2)*(C5取1)*(C2取1)*(C4取1)*(C1取1)=1440
從6個袋子取一個乘上從4顆球裡取2顆...依此類推，請問是這樣嗎？
(2, 2, 0, 0, 0, 0)
(C6取1)*(C4取2)*(C5取1)*(C2取2)=180
(3, 1, 0, 0, 0, 0)
(C6取1)*(C4取3)*(C5取1)*(C1取1)=120
(4, 0, 0, 0, 0, 0)=>其中一個袋子裝四顆球，所以就有(C6取1)=6種情況
所以共有1746種情況
但回到問題本身，所以如果m個不同的球和n個不同的球袋，
有多少種情況是至少有兩顆球被分到同一個球袋裡？
如果m>n的話，應該就是n^m？
但如果n>m時，都不知道數字的狀況下，要怎麼列出不同的情況再加以計算呢？
希望能幫忙解惑一下，謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.238.134.9 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1665667936.A.78C.html
1F：推 FanFlyAway : 可以考慮相反的狀況：「每個球袋最多只能裝一顆球 10/13 22:03
2F：→ FanFlyAway : 」，也就是說「球都要進不同的球袋」，這樣的狀況 10/13 22:03
3F：→ FanFlyAway : 會有 n!/(n-m)! 種 10/13 22:03
4F：→ FanFlyAway : 所以總共有 n^m - n!/(n-m)! 種 10/13 22:03
5F：→ FanFlyAway : 另外四球裝六袋的討論裡，狀況一和狀況二都有兩個 10/13 22:08
6F：→ FanFlyAway : 袋子裝同樣個數的球，要視為同類的袋子，所以實際 10/13 22:08
7F：→ FanFlyAway : 的種類數都要除以 2 10/13 22:08
8F：→ FanFlyAway : 例如狀況二應該是袋子有 C(6,2) 種選法，球放入袋 10/13 22:09
9F：→ FanFlyAway : 子有 C(4,2) * C(2,2) 種選法，相乘是 90 種 10/13 22:09
10F：→ cornerstone : 謝謝謝謝！竟然沒想到相反就是每袋最多只能裝一球 10/13 23:56
11F：→ cornerstone : 看完才發現：n!/(n-m)!其實是P的算法，這樣看來因為 10/13 23:58
12F：→ cornerstone : 我只考慮球>球袋或是球袋>球，如果是球袋=球，那就 10/13 23:58
13F：→ cornerstone : 變成m!或n!了（m!=n!）？也真的非常謝謝你點出我重 10/13 23:59
14F：→ cornerstone : 重複計算的部分，真的發現思維漏洞很多，謝謝指點！ 10/14 00:00