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 的大作中提到】
: n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？
|
B*****t
发帖数: 335 | 3 先求出n个不同颜色的球放入k个桶里的分法
然后分别求出n个不同颜色的球放入i(1<=i<=k-1)个桶里的分法, 然后递推求出n个不同
颜色的球放入入k个桶里，每个桶至少一个球的方法。
不过好像有个公式可以直接计算，不记得了。
【在 b******v 的大作中提到】
: n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？
|
B*****t
发帖数: 335 | 4 你这个好像是n个“相同”颜色的球放入k个桶里的答案
1
1
【在 l*****a 的大作中提到】
: 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 的大作中提到】
: 我的解法：
: 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 的大作中提到】
: 我的解法：
: 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 的大作中提到】
:
: 改进一下：
: 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 的大作中提到】
:
: 改进一下：
: 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 的大作中提到】
: 我觉得
: 第一步是 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 的大作中提到】
: 还是有重复的计算吧。 例如n=2, k=1
:
: ^k
|
r********e
发帖数: 103 | |
