p*******o
发帖数: 20 | 1 n 个不一样颜色的球, 放到n个不一样编号的罐子里面. 有m
(m<=n) 个罐子有球的概率
是多少?
我想的是: 先选m个罐子, n个球不在剩下的(n-m)个罐子的概率
是 (m/n)^n. 所以最后
的概率是 C(n,m)*(m/n)^n. 不知道对不对?
如果球一样或者罐子一样都很好做.
edit: 我的做法不对. 不能保证其它罐子每个都有球. | P*****o
发帖数: 1077 | 2 不完全对
怎么保证选出来的m个罐子，里面没有空罐子
【在 p*******o 的大作中提到】
: n 个不一样颜色的球, 放到n个不一样编号的罐子里面. 有m
: (m<=n) 个罐子有球的概率
: 是多少?
: 我想的是: 先选m个罐子, n个球不在剩下的(n-m)个罐子的概率
: 是 (m/n)^n. 所以最后
: 的概率是 C(n,m)*(m/n)^n. 不知道对不对?
: 如果球一样或者罐子一样都很好做.
: edit: 我的做法不对. 不能保证其它罐子每个都有球.
| p*******o
发帖数: 20 | 3 我也是才想到这一点, 正准备改, 就看到你的回帖了.
【在 P*****o 的大作中提到】
: 不完全对
: 怎么保证选出来的m个罐子，里面没有空罐子
| P*****o
发帖数: 1077 | 4 maybe
C(n,m) * C(n,m)*m! * m^(n-m)
【在 p*******o 的大作中提到】
: 我也是才想到这一点, 正准备改, 就看到你的回帖了.
| f*******g
发帖数: 79 | 5 C(n,m)*(m/n)^n - C(n,m-1)*(m-1/n)^n? | V*********y
发帖数: 37 | 6 可能是：
S2(n,m)*m!*C(n,m)/n^n
S2(n,m)是第二类stirling数，等于n个元素分成m个非空子集的分法数
如果罐子有编号，那么就再乘以一个m个罐子的全排列m!
然后n个罐子里取m个罐子有C(n,m)个取法
最后，总共有n^n种放法
用n=4验算了一下，把m=1,2,3,4的放法数都加起来是256种， 4^4=256，正确
不知哪位大牛可以用S2(n,m)的解析解或者递推公式验算一下普适情况。。。。
【在 p*******o 的大作中提到】
: n 个不一样颜色的球, 放到n个不一样编号的罐子里面. 有m
: (m<=n) 个罐子有球的概率
: 是多少?
: 我想的是: 先选m个罐子, n个球不在剩下的(n-m)个罐子的概率
: 是 (m/n)^n. 所以最后
: 的概率是 C(n,m)*(m/n)^n. 不知道对不对?
: 如果球一样或者罐子一样都很好做.
: edit: 我的做法不对. 不能保证其它罐子每个都有球.
| p*******o
发帖数: 20 | 7 感觉这个是对的吧. 不知道还有stirling第二类数这种东东, 学习了.
【在 V*********y 的大作中提到】
: 可能是：
: S2(n,m)*m!*C(n,m)/n^n
: S2(n,m)是第二类stirling数，等于n个元素分成m个非空子集的分法数
: 如果罐子有编号，那么就再乘以一个m个罐子的全排列m!
: 然后n个罐子里取m个罐子有C(n,m)个取法
: 最后，总共有n^n种放法
: 用n=4验算了一下，把m=1,2,3,4的放法数都加起来是256种， 4^4=256，正确
: 不知哪位大牛可以用S2(n,m)的解析解或者递推公式验算一下普适情况。。。。
| f*******g
发帖数: 79 | 8 nice solution!
【在 V*********y 的大作中提到】
: 可能是：
: S2(n,m)*m!*C(n,m)/n^n
: S2(n,m)是第二类stirling数，等于n个元素分成m个非空子集的分法数
: 如果罐子有编号，那么就再乘以一个m个罐子的全排列m!
: 然后n个罐子里取m个罐子有C(n,m)个取法
: 最后，总共有n^n种放法
: 用n=4验算了一下，把m=1,2,3,4的放法数都加起来是256种， 4^4=256，正确
: 不知哪位大牛可以用S2(n,m)的解析解或者递推公式验算一下普适情况。。。。
| l*****y
发帖数: 56 | 9 我想到的一个递推的方法是这样：
let k=number of balls, n=number of bottles, m=number of bottles that have
balls, p(k,n, m) is the probability that with k balls and n bottles, there
are m bottles which have balls.
Assume m<=n, n>0, k>0, then we have
p(0,1,0)=p(k,1,1)=1, p(0,1,1)=p(k,1,0)=0.
The recursive formula can be obtained by conditioning on the first number of
balls in the first bottle B1, i.e.
p(k,n,m)=\sum_i=0^k p(k,n,m|B1=i)pr(B1=i) =
p(k,n-1,m)[(n-1)/n]^k + \sum_i=1^k p(k-i,n-1,m-1) (1/n)^i C_i^k [(n-1)/n]^(k
-i), where C_i^k is k choose i.
Tested it with some special cases, p(n,n,n)=(n-1)!/n^(n-1), and
p(2,2,1)=0.5, it seems it works fine.
Please let me know if you see any problems.
【在 p*******o 的大作中提到】
: n 个不一样颜色的球, 放到n个不一样编号的罐子里面. 有m
: (m<=n) 个罐子有球的概率
: 是多少?
: 我想的是: 先选m个罐子, n个球不在剩下的(n-m)个罐子的概率
: 是 (m/n)^n. 所以最后
: 的概率是 C(n,m)*(m/n)^n. 不知道对不对?
: 如果球一样或者罐子一样都很好做.
: edit: 我的做法不对. 不能保证其它罐子每个都有球.
| P*****o
发帖数: 1077 | 10 S2是什么
其实这个很简单
n里面取m个盒子,C(n,m)
n个球里取m个，m个球排列，然后放在m个盒子里，这样每个盒子至少有一个球，C(n,m)
*m!
剩下的(n-m)个球，随意从m个盒子选一个放，(n-m)^m
【在 V*********y 的大作中提到】
: 可能是：
: S2(n,m)*m!*C(n,m)/n^n
: S2(n,m)是第二类stirling数，等于n个元素分成m个非空子集的分法数
: 如果罐子有编号，那么就再乘以一个m个罐子的全排列m!
: 然后n个罐子里取m个罐子有C(n,m)个取法
: 最后，总共有n^n种放法
: 用n=4验算了一下，把m=1,2,3,4的放法数都加起来是256种， 4^4=256，正确
: 不知哪位大牛可以用S2(n,m)的解析解或者递推公式验算一下普适情况。。。。
| | | f*******g
发帖数: 79 | 11 这样的话，有些case 会被重复计算，比如 盒子有 ball #1 #2 的例子。
m)
【在 P*****o 的大作中提到】
: S2是什么
: 其实这个很简单
: n里面取m个盒子,C(n,m)
: n个球里取m个，m个球排列，然后放在m个盒子里，这样每个盒子至少有一个球，C(n,m)
: *m!
: 剩下的(n-m)个球，随意从m个盒子选一个放，(n-m)^m
| P*****o
发帖数: 1077 | 12 i see
thanks!
n,
【在 f*******g 的大作中提到】
: 这样的话，有些case 会被重复计算，比如 盒子有 ball #1 #2 的例子。
:
: m)
| C***U
发帖数: 2406 | 13 容斥原理应该可以做
【在 p*******o 的大作中提到】
: n 个不一样颜色的球, 放到n个不一样编号的罐子里面. 有m
: (m<=n) 个罐子有球的概率
: 是多少?
: 我想的是: 先选m个罐子, n个球不在剩下的(n-m)个罐子的概率
: 是 (m/n)^n. 所以最后
: 的概率是 C(n,m)*(m/n)^n. 不知道对不对?
: 如果球一样或者罐子一样都很好做.
: edit: 我的做法不对. 不能保证其它罐子每个都有球.
| y******6
发帖数: 61 | 14 wikipedia does have stirling number of the second hand.
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kin
Also, you may find the explicit formula for {n,k}.
【在 V*********y 的大作中提到】
: 可能是：
: S2(n,m)*m!*C(n,m)/n^n
: S2(n,m)是第二类stirling数，等于n个元素分成m个非空子集的分法数
: 如果罐子有编号，那么就再乘以一个m个罐子的全排列m!
: 然后n个罐子里取m个罐子有C(n,m)个取法
: 最后，总共有n^n种放法
: 用n=4验算了一下，把m=1,2,3,4的放法数都加起来是256种， 4^4=256，正确
: 不知哪位大牛可以用S2(n,m)的解析解或者递推公式验算一下普适情况。。。。
| L**********u
发帖数: 194 | | w*****k
发帖数: 177 | 16 C(n,m)*[C(m,n-1)]
【在 p*******o 的大作中提到】
: n 个不一样颜色的球, 放到n个不一样编号的罐子里面. 有m
: (m<=n) 个罐子有球的概率
: 是多少?
: 我想的是: 先选m个罐子, n个球不在剩下的(n-m)个罐子的概率
: 是 (m/n)^n. 所以最后
: 的概率是 C(n,m)*(m/n)^n. 不知道对不对?
: 如果球一样或者罐子一样都很好做.
: edit: 我的做法不对. 不能保证其它罐子每个都有球.
| p*****r
发帖数: 341 | 17 C(n,m)*(m/n)^n
n个罐子选m个有C(n,m)种选法，n个球进m个罐子有m^n种摆法。一共有n^n种摆法。
请指正！ | a*****t
发帖数: 30 | 18 C(n,m)*(m/n)^n 种方法中 m个罐子可能为空。
修正一下就是楼上的结果；
C(n,m)*(m/n)^n - C(n,m-1)*(m-1/n)^n
【在 p*****r 的大作中提到】
: C(n,m)*(m/n)^n
: n个罐子选m个有C(n,m)种选法，n个球进m个罐子有m^n种摆法。一共有n^n种摆法。
: 请指正！
|
|
