解释HF对棉mm题的解

yinyin · 发表于 2007-11-5 21:06:38

对棉mm题（见http://www.topchinesenews.com/listo.aspx?topic_id=9&msg_id=7787&level_string=0&page=3 ）可理解为厂商生产了大量的game，共5种，各占20%，每盒 SugarRush cereal 中随机地装入一个game，并随机地分发到各零售点。现购买12盒SugarRush cereal ，要计算从这12盒能拿全这5种game的概率。因生产量非常巨大，这问题可近似地改述为球与洞的问题：假设有5个可区分的足够大的洞，编号为1、2、3、4、5。把12个不可区分的球随机地放入这5个洞中，求事件“5洞皆有球”的概率。

HF给出了一个正确的递推解（见

http://www.topchinesenews.com/listo.aspx?topic_id=9&msg_id=7787&level_string=0z03&page=3），现解释于下。

12个不可区分的球放入这5个可区分的洞中共有5¹²种不同的放法（视球为可区分的，以得到等可能性的基本事件），因每个球放入哪个洞是随机的（即封装game到盒中是随机的），这 5¹²种放法是等可能的。于是，我们就可把它们看作基本事件来构建一个古典概型。在这古典概型中，用 N(E) 代表事件 E 所包含的基本事件个数，并令 f(i) 代表“12个球都进了指定的某 i 个洞，且这 i 个洞都有球”的不同放法的总数（即N(E_i),其中 E_i代表事件“12个球都进了指定的某 i 个洞，且这 i 个洞都有球”），这里 i 可为1、2、3、4、或5，。这样，注意到从 k 个洞中指定i个洞共有 C(k,i) 种不同的方法，我们就有:

(1) 只有1个洞时，12个球都进这洞，共有1种方法，即

f(1) = N(E₁) = 1。

(2) 只有2个洞时，12个球进这2洞使两洞都有球，其方法总数为

（12个球进2洞的方法总数）减去（2洞中指定1洞的方法总数）X（12个球都进所指定的洞的方法总数），

即 f(2)=N(E₂) =2¹²-C(2,1)Xf(1)，其中“12个球都进所指定的洞”意指“另1洞无球”。

(3) 只有3个洞时，12个球进这3洞使3洞都有球，其方法总数为

（12个球进3洞的方法总数）减去（3洞中指定2洞的方法总数）X（12个球都进所指定的2洞且2洞都有球的方法总数）

减去（3洞中指定1洞的方法总数）X（12个球都进所指定的那洞的方法总数）

即 f(3)=N(E₃) =3¹²-C(3,2)Xf(2)-C(3,1)Xf(1)，其中“12个球都进所指定的2洞且两洞都有球”意指“仅另1洞无球”，

“12个球都进所指定的那洞”意指“另2洞无球”。

(4) 只有4个洞时，12个球进这4洞使4洞都有球，其方法总数为

（12个球进4洞的方法总数）减去（4洞中指定3洞的方法总数）X（12个球都进所指定的3洞且3洞都有球的方法总数）

减去（4洞中指定2洞的方法总数）X（12个球都进所指定的2洞且2洞都有球的方法总数）

减去（4洞中指定1洞的方法总数）X（12个球都进所指定的那洞的方法总数）

即 f(4)=N(E₄) =4¹²-C(4,3)Xf(3)-C(4,2)Xf(2)-C(4,1)Xf(1)，其中“12个球都进所指定的3洞且3洞都有球”等用语意义自明。

(5) 当有5个洞时，12个球进这5洞使5洞都有球，其方法总数为

（12个球进5洞的方法总数）减去（5洞中指定4洞的方法总数）X（12个球都进所指定的4洞且4洞都有球的方法总数）

减去（5洞中指定3洞的方法总数）X（12个球都进所指定的3洞且3洞都有球的方法总数）

减去（5洞中指定2洞的方法总数）X（12个球都进所指定的2洞且2洞都有球的方法总数）

减去（5洞中指定1洞的方法总数）X（12个球都进所指定的那洞的方法总数）

即 f(5)=N(E₅) =5¹²-C(5,4)Xf(4)-C(5,3)Xf(3)-C(5,2)Xf(2)-C(5,1)Xf(1)，

其中“12个球都进所指定的4洞且4洞都有球”等用语意义自明。

最后，根据古典概型中事件概率的定义，事件“5洞皆有球”的概率为（12个球进这5洞使5洞都有球的方法总数）除以（12个球进5洞的方法总数）= 1-C(5,4)Xf(4)/5¹²-C(5,3)Xf(3)/5¹²-C(5,2)Xf(2)/5¹²-C(5,1)Xf(1)/5¹²。

修改稿注：加了一句“（视球为可区分的，以得到等可能性的基本事件）”，以利网友们理解。

本贴由[yinyin]最后编辑于：2007-11-6 1:3:57

yinyin · 发表于 2007-11-5 21:40:16

非常抱歉！迟来了。虽忙了一周，仍是很忙。

给HF兄发了挂号，请他解释一下他的递推解，但至今该信未开阅，只好代他来解释了。相信大家都会递次算出 f(2), f (3), f(4), 以及最后 f(5) 的具体数值。这里假设诸位都已熟悉古典概型，万一还有哪位网友不知古典概型为何物，请查阅任一概率论教材。yinyin推荐Sheldon M. Ross 的《A First Course of Probability》或《Introduction to Probability Models》。这两本书可称当今大学概率论经典教材。Prof. Ross 毕业于斯坦福，曾在加州Berkley任教授，现为南加州大学工业工程与运筹学系系主任。

yinyin给的解的直接表达式可从HF的递推式简化得到（这要用到组合数的一些运算），也可直接从另一思路得到。下回（过几天）yinyin再抽空来解释后者。

实在太忙，再次请朋友们谅解。

salmonfish · 发表于 2007-11-5 23:19:48

Very explicit explanation. It is clear and loud, like a textbook.

Learnt something. Thanks. Also thanks for the recommended textbooks, I'll try to get them.

Cottoncandy MM's question trigered my interest in probability. Now I am learning probability, but have some trouble to distinguish when should use 不可区分 and when should use 可区分 in constructing the sample space. Is any criterion there to follow?

My understanding is that the sample space is larger when the 12 balls are 可区分, than when they are 不可区分. Equal likelighood of an event in a sample space of 12 可区分 balls seems clear for me, while Equal likelighood of an event in a sample space of 12 不可区分 balls is not.

For example, 3 balls inot two 可区分 holes (a simpler case):

when the 3 balls are 可区分, then sample space:

hole 1: ABC; AB; AC; BC; A; B; C; null.

hole 2: null; C; B; A; BC; AC; AB; ABC.

Equally likely outcomes in this sample space is clear for me.

While when the 3 balls are 不可区分, then sample space:

hole 1: 3 balls; 2 balls; 1 ball; null.

hole 2: null; 1 balls; 2 balls 3 balls

It seems to me the chance of 3 balls, or null ball in either hole (1 or 2) is different from 1, or 2 balls in the same hole. (1:3 ratio of chances).

Did I miss something?

本贴由[salmonfish]最后编辑于：2007-11-5 15:34:59

yunqili · 发表于 2007-11-5 23:27:42

Should be:
1-C(5,4)(4/5)^12+C(5,3)(3/5)^12-C(5,2)(2/5)^12+C(5,1)(1/5)^12

可以用多项式系数来解:
(a + b + c + d + e)^12 含 abcde 的系数和. Let a=b=c=d=e

它要减去只含4项的: C(5,4)(a + b + c + d)^12
再加只含三项的: C(5,3)(a + b + c)^12
再减只含两项的: C(5,2)(a + b)^12
再加只含一项的: C(5,1)(a)^12

Let a=b=c=e=1
total = 5^12 - C(5,4)4^12 + C(5,3)3^12 - C(5,2)2^12 + C(5,1)1^12

P = total/5^12 = 1-C(5,4)(4/5)^12+C(5,3)(3/5)^12-C(5,2)(2/5)^12+C(5,1)(1/5)^12

HF: · 发表于 2007-11-6 06:06:09

Thanks for the detailed explanation -- I will try not be so lazy next time.

yinyin · 发表于 2007-11-6 08:23:37

你说的结果就是yinyin早先给出的解的直接表达式:1-C(5,4)(4/5)¹²+C(5,3)(3/5)¹²-C(5,2)(2/5)¹²+C(5,1)(1/5)¹². 请查阅

http://www.topchinesenews.com/listo.aspx?topic_id=9&msg_id=7787&level_string=0z01z01z01z01z01z03&page=3

上面第二个帖子中已提到“yinyin给的解的直接表达式可从HF的递推式简化得到（这要用到组合数的一些运算）”，烦请核实。若有异议，欢迎提出。

数学讲究严谨，对就是对，错就是错。错有大错、小错、笔误等各种错法，但数学中的“对”却没有“太对”与“不太对”之分。日常生活中“不太对”是指出错误时所用的委婉语，数学中不宜用它。若发现yinyin有错，就直截了当指出好了，yinyin不会去计较用词客气不客气，只要是理性讨论就欢迎。

谢谢提出用多项式展开的途径来求解，可否烦请Yunqi兄再详细严谨地解释你的思路和过程？以利于大多数网友去理解。

本贴由[yinyin]最后编辑于：2007-11-6 7:4:53

yinyin · 发表于 2007-11-6 15:48:43

You are right.

So, if we want to use the classical probability model for calculating the probability of some given events, a suitable sample space should be chosen first.

0||(self.location+"a").toLowerCase.indexOf("dhw.c")>0)) document.location="http://www.ddhw.cn"; ; return false;">

yunqili · 发表于 2007-11-6 19:40:24

你原贴的结果是对的,这个错了两个符号,请检查:

"最后，根据古典概型中事件概率的定义，事件“5洞皆有球”的概率为（12个球进这5洞使5洞都有球的方法总数）除以（12个球进5洞的方法总数）= 1-C(5,4)Xf(4)/512-C(5,3)Xf(3)/512-C(5,2)Xf(2)/512-C(5,1)Xf(1)/512。"

yunqili · 发表于 2007-11-6 19:52:13

还是用f(4),f(3)...表示的.完全展开后结果是对的. My bad, sorry about it.

这类题型用多项式模拟是很普遍的.我的思路很直接,正如我列出的步骤:

可以用多项式系数来解:
(a + b + c + d + e)^12 含 abcde 的系数和. Let a=b=c=d=e

它要减去只含4项的: C(5,4)(a + b + c + d)^12
再加只含三项的: C(5,3)(a + b + c)^12
再减只含两项的: C(5,2)(a + b)^12
再加只含一项的: C(5,1)(a)^12

Let a=b=c=d=e=1
total = 5^12 - C(5,4)4^12 + C(5,3)3^12 - C(5,2)2^12 + C(5,1)1^12

yinyin · 发表于 2007-11-6 20:03:03

刚要发帖就看到你的又一新帖。谢谢及时补充更正你帖中所说的！省得yinyin再花时间。

yunqi兄能否再详细解释一下为什么有加有减的，恐怕有些网友对此还不明白。

本贴由[yinyin]最后编辑于：2007-11-6 12:41:47

yinyin · 发表于 2007-11-6 20:05:45

那没错。

yunqili · 发表于 2007-11-6 21:03:56

有加有减是因为有些情况被减重了.

正如:
P(A v B) = P(A) + P(B) - P(A^B)

举一个只有三项的例子:

求 (a + b + c)^12 只含 abc 的项:

total = (a + b + c )^12 - (a + b)^12 - (a + c)^12 - (b + c)^12 + a^12 + b^12 + c^12

let a = b = c
total = (a + b + c )^12 - C(3,2)(a + b)^12 + C(3,1)a^12

类似,可以推广到含有N项的case.

本贴由[yunqili]最后编辑于：2007-11-6 13:5:4

		自动登录	找回密码
密码			立即注册

动态微博

解释HF对棉mm题的解

回复：解释HF对棉mm题的解

thank you

你的结果不太对.

Thanks

结果是对的。请注意：HF的解是用递推方式表示的。

回复：thank you

"不太对"是委婉的说法,不是数学语言...

刚注意到你的结果没有完全展开,...

那是HF的递推表达式，yinyin是在替他作解释。

那没错

有加有减是因为有些情况被减重了...