问道题(分球问题)# JobHunting - 待字闺中
i*t
1 楼
准备开始吃沙拉加肌肉的那种
之前随便买了一个沙拉酱 味道一般
大家推荐一个吧 就是自己吃起来觉得很好的就行
具体到牌子 和口味 这样我就能直接锁定目标了
thx
之前随便买了一个沙拉酱 味道一般
大家推荐一个吧 就是自己吃起来觉得很好的就行
具体到牌子 和口味 这样我就能直接锁定目标了
thx
b*v
2 楼
n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？
l*a
3 楼
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个桶里，每个桶至少一个球，有多少种分法？
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
4 楼
先求出n个不同颜色的球放入k个桶里的分法
然后分别求出n个不同颜色的球放入i(1<=i<=k-1)个桶里的分法, 然后递推求出n个不同
颜色的球放入入k个桶里，每个桶至少一个球的方法。
不过好像有个公式可以直接计算，不记得了。
【在 b******v 的大作中提到】
: n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？
然后分别求出n个不同颜色的球放入i(1<=i<=k-1)个桶里的分法, 然后递推求出n个不同
颜色的球放入入k个桶里，每个桶至少一个球的方法。
不过好像有个公式可以直接计算，不记得了。
【在 b******v 的大作中提到】
: n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？
B*t
5 楼
你这个好像是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?
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
6 楼
我的解法：
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)
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
7 楼
这个好像不对，有很多重复的计算
例如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)
例如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
8 楼
改进一下：
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
9 楼
还是有重复的计算吧。 例如n=2, k=1
^k
【在 s******i 的大作中提到】
:
: 改进一下：
: 1. 从n个球中随机选出k个，有(n,k)种选法；
: 2. 把剩下的n-k个球随机放入k个桶中，由于每个球都有可能进入任意一个桶，(n-k)^k
: (n,k)*(n-k)^k
: 原因：
: 之前的第二步不需要，因为每个桶都是一样的。
^k
【在 s******i 的大作中提到】
:
: 改进一下：
: 1. 从n个球中随机选出k个，有(n,k)种选法；
: 2. 把剩下的n-k个球随机放入k个桶中，由于每个球都有可能进入任意一个桶，(n-k)^k
: (n,k)*(n-k)^k
: 原因：
: 之前的第二步不需要，因为每个桶都是一样的。
s*l
10 楼
我觉得
第一步是 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
: 原因：
: 之前的第二步不需要，因为每个桶都是一样的。
第一步是 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
11 楼
如果假设桶都相同，第一步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
因为按顺序把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
12 楼
(n,k)*(n-k)^k, 第一个是组合不是排列
if n=2, k=1 => C2.1*(2-1)^1 = 2
例如 一个红球，一个篮球，一个桶：两个可能
【在 B*****t 的大作中提到】
: 还是有重复的计算吧。 例如n=2, k=1
:
: ^k
if n=2, k=1 => C2.1*(2-1)^1 = 2
例如 一个红球，一个篮球，一个桶：两个可能
【在 B*****t 的大作中提到】
: 还是有重复的计算吧。 例如n=2, k=1
:
: ^k
r*e
13 楼
相关阅读
后天到Las Vegas 机场，驾照过期三天，可否租车？请教！急急C++ Q 99-102OPT寄了几个星期了网上还查不到中部农村offer问个easy问题请问H1B 网上批了，approval notice多久能寄到呀求一般system design问题解题思路miss掉paypal的onne hour evaluationOnsite完等消息中，10个包子【急问】新旧老板发工资有一天overlap了要不要紧？请教一个在美与人打交道的问题 找工作方面明天LP dream company的onsite，求祝福谁对design pattern比较熟？求助：办OPT的时候有一份旧的I20没有复印现在H1B配额已经用到发疯了CS专业，到底要不要1月出去实习呀。。。伤心。。。。onsite归来，也求祝福~~OPT快过期了, 申请F２还是上community college请教关于IBM TJ Watson附近的住房信息