吃面问题系列之二

056254628

一家店会做n+m种口味的面,其中n种为粤菜系列，另m种为川菜系列，每天老板会随机推出其中一种,老板规定，吃遍任何一个系列的面都会有奖。那么顾客平均要去多少次才能得奖? 将所求的次数的期望值记作f(n,m). 显而易见 f(1,1)=1

gxqcn

感觉这个可比先前的吃面问题难多了：http://bbs.emath.ac.cn/thread-1873-1-1.html

mathe

假设$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)$

wayne

二阶的。。。 还是很难求啊

wayne

待会吃点面食，找找灵感~~

056254628

用电脑模拟吃面过程： 下式似乎成立。 f(n,1)=n

mathe

是的。其实f(n,2)的表达式也挺好计算。但是n,m都比较大时就比较难用表达式来表示了

056254628

设$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$

mathe

期望数好像是不能这样相减的:$a_1+a_2-a_0$

mathe

经检验，你的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 >