b******v 发帖数: 1493 | 1 n个不同颜色的球分入k个桶里,每个桶至少一个球,有多少种分法? |
l*****a 发帖数: 14598 | 2 0-1-2-3-4-5-.........-(n-2)-(n-1)
there are n-1 pairs as 0-1,1-2,2-3....
if we cut one pair,we can put them into 2桶,each 桶 has at least 1
if we cut k-1 pair,we can put them into K桶,each 桶 has at least 1
then we have C(n-1,k-1) ways to cut them.
is this right?
【在 b******v 的大作中提到】![](/moin_static193/solenoid/img/up.png) : n个不同颜色的球分入k个桶里,每个桶至少一个球,有多少种分法?
|
B*****t 发帖数: 335 | 3 先求出n个不同颜色的球放入k个桶里的分法
然后分别求出n个不同颜色的球放入i(1<=i<=k-1)个桶里的分法, 然后递推求出n个不同
颜色的球放入入k个桶里,每个桶至少一个球的方法。
不过好像有个公式可以直接计算,不记得了。
【在 b******v 的大作中提到】![](/moin_static193/solenoid/img/up.png) : n个不同颜色的球分入k个桶里,每个桶至少一个球,有多少种分法?
|
B*****t 发帖数: 335 | 4 你这个好像是n个“相同”颜色的球放入k个桶里的答案
1
1
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 0-1-2-3-4-5-.........-(n-2)-(n-1) : there are n-1 pairs as 0-1,1-2,2-3.... : if we cut one pair,we can put them into 2桶,each 桶 has at least 1 : if we cut k-1 pair,we can put them into K桶,each 桶 has at least 1 : then we have C(n-1,k-1) ways to cut them. : is this right?
|
r*****a 发帖数: 23 | 5 我的解法:
1. 从n个球中随机选出k个,有(n,k)种选法;
2. 把选出的k个球放入k个桶中,每个桶一个球,共有k!种放法;
3. 把剩下的n-k个球随机放入k个桶中,由于每个球都有可能进入任意一个桶,所以对
每个球来说,有k种可能,n-k个球有n^(n-k)种可能
4. 总的分法是(n,k)*k!*n^(n-k) |
B*****t 发帖数: 335 | 6 这个好像不对,有很多重复的计算
例如n=2, k=1
【在 r*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的解法: : 1. 从n个球中随机选出k个,有(n,k)种选法; : 2. 把选出的k个球放入k个桶中,每个桶一个球,共有k!种放法; : 3. 把剩下的n-k个球随机放入k个桶中,由于每个球都有可能进入任意一个桶,所以对 : 每个球来说,有k种可能,n-k个球有n^(n-k)种可能 : 4. 总的分法是(n,k)*k!*n^(n-k)
|
s******i 发帖数: 44 | 7
改进一下:
1. 从n个球中随机选出k个,有(n,k)种选法;
2. 把剩下的n-k个球随机放入k个桶中,由于每个球都有可能进入任意一个桶,(n-k)^k
(n,k)*(n-k)^k
原因:
之前的第二步不需要,因为每个桶都是一样的。
【在 r*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的解法: : 1. 从n个球中随机选出k个,有(n,k)种选法; : 2. 把选出的k个球放入k个桶中,每个桶一个球,共有k!种放法; : 3. 把剩下的n-k个球随机放入k个桶中,由于每个球都有可能进入任意一个桶,所以对 : 每个球来说,有k种可能,n-k个球有n^(n-k)种可能 : 4. 总的分法是(n,k)*k!*n^(n-k)
|
B*****t 发帖数: 335 | 8 还是有重复的计算吧。 例如n=2, k=1
^k
【在 s******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 改进一下: : 1. 从n个球中随机选出k个,有(n,k)种选法; : 2. 把剩下的n-k个球随机放入k个桶中,由于每个球都有可能进入任意一个桶,(n-k)^k : (n,k)*(n-k)^k : 原因: : 之前的第二步不需要,因为每个桶都是一样的。
|
|
s********l 发帖数: 998 | 9 我觉得
第一步是 order matters and element are not replaced 的情况
所以 1: n!/(n-k)!
2: k^(n-k)
最后 k^(n-k) * n!/(n-k)!
^k
【在 s******i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 改进一下: : 1. 从n个球中随机选出k个,有(n,k)种选法; : 2. 把剩下的n-k个球随机放入k个桶中,由于每个球都有可能进入任意一个桶,(n-k)^k : (n,k)*(n-k)^k : 原因: : 之前的第二步不需要,因为每个桶都是一样的。
|
h*******e 发帖数: 225 | 10 如果假设桶都相同,第一步P(n,k)就不对。如果假设桶也各不相同,第二步仍然不对,
因为按顺序把a, b扔进桶X,和把b, a扔进X是一样的,但是你的算法会分别算。
这是经典的组合数了,google第二类Stirling数。
【在 s********l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得 : 第一步是 order matters and element are not replaced 的情况 : 所以 1: n!/(n-k)! : 2: k^(n-k) : 最后 k^(n-k) * n!/(n-k)! : : ^k
|
s******i 发帖数: 44 | 11 (n,k)*(n-k)^k, 第一个是组合不是排列
if n=2, k=1 => C2.1*(2-1)^1 = 2
例如 一个红球,一个篮球,一个桶:两个可能
【在 B*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还是有重复的计算吧。 例如n=2, k=1 : : ^k
|
r********e 发帖数: 103 | |