分球问题总结

(1) n个球分入k个桶里，有多少种分法？（假设球不可分辨）

解答：把n个球排成一排，中间插k-1个挡板。这k-1个挡板隔开的k个区间对应放入相应桶的球的数目。从而答案是C(n+k-1, k-1).

(2) n个球分入k个桶里，要求每个桶至少一个球，有多少种分法？（假设球不可分辨）

解答：可以先给每个桶分配一个球，余下的n-k个球再任意分入k个桶里，这样共有C(n-k+k-1, k-1) = C(n-1, k-1)种分法。

(3) n个不同颜色的球分入k个桶里，有多少种分法？

解答：每个球有k种选择，所以答案是$k^n$.

(4) n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？

解答：

设f(n,k)为把n个不同颜色的球扔到k个桶里，每个桶至少一个球的扔法总数。由于第3题中把n个球随机分配到k个桶里，可能出现这些球分别只在$1,2, \cdots, k$个桶里的情况，所以我们有下面这个递推公式：

$$k^n = C(k,1)*f(n,1)+C(k,2)*f(n,2)+...+C(k,k-1)*f(n,k-1)+f(n,k)$$

当只有一个桶时，显然有f(n,1) = 1。由此根据上述递推公式可以用数学归纳法得到

$$f(n,k) = \sum_{i=0}^{k-1} (-1)^i C(k,i) (k-i)^n$$