吃面问题系列之二

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 >