[中學] 排組的問題

[cornerstone (cornerstone)]

不好意思，又想請教大家一題數學問題，
有附上我的想法，但需要板上朋友們幫忙。

有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://www.ptt.cc/bbs/Math/M.1665667936.A.78C.html
推 FanFlyAway  : 可以考慮相反的狀況：「每個球袋最多只能裝一顆球
→ FanFlyAway  : 」，也就是說「球都要進不同的球袋」，這樣的狀況
→ FanFlyAway  : 會有 n!/(n-m)! 種
→ FanFlyAway  : 所以總共有 n^m - n!/(n-m)! 種
→ FanFlyAway  : 另外四球裝六袋的討論裡，狀況一和狀況二都有兩個
→ FanFlyAway  : 袋子裝同樣個數的球，要視為同類的袋子，所以實際
→ FanFlyAway  : 的種類數都要除以 2
→ FanFlyAway  : 例如狀況二應該是袋子有 C(6,2) 種選法，球放入袋
→ FanFlyAway  : 子有 C(4,2) * C(2,2) 種選法，相乘是 90 種
→ cornerstone : 謝謝謝謝！竟然沒想到相反就是每袋最多只能裝一球
→ cornerstone : 看完才發現：n!/(n-m)!其實是P的算法，這樣看來因為
→ cornerstone : 我只考慮球>球袋或是球袋>球，如果是球袋=球，那就
→ cornerstone : 變成m!或n!了（m!=n!）？也真的非常謝謝你點出我重
→ cornerstone : 重複計算的部分，真的發現思維漏洞很多，謝謝指點！