Tuesday, April 27, 2010

分球问题总结

(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\]

No comments:

Visitors