吃面问题系列之二
一家店会做n+m种口味的面,其中n种为粤菜系列，另m种为川菜系列，每天老板会随机推出其中一种,老板规定，吃遍任何一个系列的面都会有奖。那么顾客平均要去多少次才能得奖?将所求的次数的期望值记作f(n,m). 显而易见f(1,1)=1 感觉这个可比先前的吃面问题难多了：http://bbs.emath.ac.cn/thread-1873-1-1.html 假设$E(x,y)$为顾客已经吃过$x$种粤菜$y$种川菜以后，平均还需要吃的次数。
那么已知
$E(n,y)=E(x,m)=0$
$E(x,y)=1+{x+y}/{n+m}E(x,y)+{n-x}/{n+m}E(x+1,y)+{m-y}/{n+m}E(x,y+1)$
这是一个二阶的递推式，求$E(0,0)$ 二阶的。。。
还是很难求啊 待会吃点面食，找找灵感~~ 用电脑模拟吃面过程：下式似乎成立。
f(n,1)=n 是的。其实f(n,2)的表达式也挺好计算。但是n,m都比较大时就比较难用表达式来表示了 本帖最后由 056254628 于 2009-11-10 10:49 编辑
设$a_1$ 为吃遍粤菜系列面的次数期望值
设$a_2$ 为吃遍川菜系列面的次数期望值
设$a_0$ 为既吃遍川菜系列面也吃遍粤菜系列面（及吃遍所有面）的次数期望值
那么：
$a_1= (n+m)*\sum_{i=1}^{n}1/i$
$a_2= (n+m)*\sum_{i=1}^{m}1/i$
$a_0= (n+m)*\sum_{i=1}^{n+m}1/i$
而题目所求的次数期望值f(n,m)=$a_1+a_2-a_0$
=$(n+m)*\sum_{i=1}^{n}1/i+(n+m)*\sum_{i=1}^{m}1/i-(n+m)*\sum_{i=1}^{n+m}1/i$
即：f(n,m)=$(n+m)*(\sum_{i=1}^{m}1/i-\sum_{i=1}^{m}1/(n+i))$
--------------------
从上述公式计算得：
$f(n,1)=(n+1)*(1-1/(n+1))=n$
$f(2,2)=4*(1+1/2-1/3-1/4)=11/3$
$f(3,2)=5*(1+1/2-1/4-1/5)=21/4$
$f(5,3)=8*(1+1/2+1/3-1/6-1/7-1/8)=11+4/21=235/21$ 期望数好像是不能这样相减的:$a_1+a_2-a_0$ 经检验，你的f(4,3)的值开始错误了
(10:53) gp > ?E
E(x, y, n, m) = if(x>=n||y>=m,0,(n+m+(n-x)*E(x+1,y,n,m)+(m-y)*E(x,y+1,n,m))/(n+m
-x-y))
(10:53) gp > ?F
F(m, n) = E(0,0,m,n)
(10:53) gp > F(4,3)
%4 = 139/15
(10:53) gp >
页:
[1]
2