N個相同的球，放入M個相同的盒子中，允許有盒子為空，請問有多少種方法？

---

涉及分拆數，沒有close form.

答案是p(n,1)+p(n,2)+…+p(n,k).p(n,k)是分拆數

---

這麼多回答擋板或者不定方程整數解的是怎麼回事啊？

@王芊的答案是正確的。

關於這類題目的總結可以參見：

http://pan.baidu.com/s/1jGFBSNk

裡面有一張 37balabala.jpg，總結了所有情況（不知道為什麼我每次傳圖到知乎都掛，就傳網盤了）。

劃分數沒有具體的表達式，可以用生成函數計算。

---

十個不同的球放入十個不同的盒子里，哈哈真簡單，咦不對，是相同的，哇塞，都是相同的，好難啊！

不如退一步

假如我給某個東西加上順序，比如說盒子1，2，3，4......

這是什麼問題呢？

n個未知數之和為M，求整數解

我們假想m是同等數量的小珠子，我們要做的是用隔板隔開

一共需要n-1個隔板

只要把球與隔板隨機排列就行了

每一個排法對應一個解

這個求法對應概率上的partition

把一個集合分成兩個集合，兩集合內部順序不重要，兩集合相對位置才重要

故根據partition，抽法就是從n+m-1中抽出m個。

因為每一個解，是有順序的，101不等於011然而我們的盒子是沒有編號的。

故最後每種組合對應m!排列

partition結果處以m!即為答案

---

這個問題可以遞歸的解決。

首先我們假設2,1,1和1,2,1是一種相同的放法。

定義f(n, m)為n個球放入m個盒中的放法數目。

1. 當m&>n, 則總會有m-n個盒子空著，去掉他們對總的放法不產生影響，即 if(m &> n) f(n, m) = f(n, n)

2. 當m&<=n，可分兩種情況：

• 至少有一個盒子空著，則 f(n, m) = f(n, m-1);

• 所有盒子都有球，我們可以從每個盒子中拿掉一個球而不影響總的放法，則 f(n, m) = f(n-m, m);

所以對於m&<=n的情況，有 f(n, m)=f(n, m-1) + f(n-m, m)

代碼：

int f(n, m)

{

if(m == 1 || n == 0) return 1;

if(m &> n) return f(n, n);

return f(n, m-1) + f(n-m, m);

}

---

對其他的答案做一個補充：

這個問題在組合數學(combinatorics)里叫做stars and bars問題，詳見https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)。

通過隔板法解決。

PS：其實還有更高端的題目，比如增加一個條件，球的顏色各不相同，就更好玩了。其實都是數論（Number Theory）裡面的問題，詳見Composition (combinatorics)以及Partition (number theory)。

這裡有個計算器，可以直接算結果的，Partition calculators using java applets。結果是很嚇人！

---

推薦閱讀：