Quod Erat Demonstrandum

2010/06/17

重複數算一例

Filed under: Additional / Applied Mathematics,HKALE — johnmayhk @ 11:05 上午
Tags:

擬了一道長題:

第一,我沒有說明該「骰子」的運作:所謂得出的「花」應是指在骰子底部沒有題示出來的那個花!sosad…

第二,明眼人知道我是迆出,因為,用「容斥原理」,兩步KO,變成最多值 4 分的短題,見

http://www.hkms-nss.net/discuz/home/space.php?uid=423&do=blog&id=38

但估計不會有太多同學會用「容斥原理」,所以我欺瞞地把題目變成長題,用愚蠢的 binomial distribution 的手法,利用諸如

\displaystyle \sum_{k = 0}^n C_r^n = 2^n\displaystyle \sum_{k = 0}^n C_r^n (2^n) = 3^n

的關係慢慢得出結果,甚為愚拙。

Part (a) 想問,擲「骰」n 次,得出四種「花」的概率。

我就分別計算

僅有 1 種花之概率,即 p_1 = \frac{1}{4^{n - 1}}

僅有 2 種花之概率,即 p_2 = \frac{6(2^n - 2)}{4^{n - 1}}

僅有 3 種花之概率,即 p_3 = \frac{3^n - 3(2^n) + 3}{4^{n - 1}}; [看上面連結那篇的結果]

從而得出

得 4 種花之概率,即 p_4 = 1 - p_1 - p_2 - p_3 = \frac{4^{n - 1} - 3^n + 3(2^{n - 1}) - 1}{4^{n - 1}}

同事查卷時提出計算「僅有 3 種花之概率」的方法如下:

p_3 = C_3^4(\frac{3}{4})^n - p_1 - p_2 = \frac{3^n - 3(2^{n - 1}) + 2}{4^{n - 1}}

第一項 C_3^4(\frac{3}{4})^n 不過是 n 次擲骰出現(最多)三種花的概率,減去「僅有 1 種花」和「僅有 2 種花」之概率,不就是「僅有 3 種花」的概率嗎?

究竟 p_3

\frac{3^n - 3(2^n) + 3}{4^{n - 1}} 還是 \frac{3^n - 3(2^{n - 1}) + 2}{4^{n - 1}} ?

當然這道經典舊題,答案不容置疑,但授課員的難題是,如何解釋同事做法之問題所在。

同事的方法是好方法,不過正確做法應是

p_3 = C_3^4[(\frac{3}{4})^n - C_1^3(\frac{1}{4})^n - C_2^3(\frac{2^n - 2}{4^n})]

當中的 (\frac{3}{4})^n 就是(最多)出現某三種花(比方說 \spadesuit, \heartsuit\clubsuit)之概率。那麼,

C_1^3(\frac{1}{4})^n 就是該三種花中「僅有 1 種花」出現之概率;

C_2^3(\frac{2^n - 2}{4^n}) 就是該三種花中「僅有 2 種花」出現之概率。

好了,考慮完(\spadesuit, \heartsuit, \clubsuit)可以考慮其他的諸如(\spadesuit, \heartsuit, \diamondsuit),所以最後乘上 C_3^4

同事的做法是一開始乘 C_3^4,得 C_3^4(\frac{3}{4})^n,當中有重複數算。

因為起碼,分子中的 3^n,其中包含了(比如說考慮某三種花可能出現的情況下)全是 \spadesuit 的情況,這對於全局來說,是一個情況(case)(注,僅出現一種花共有 4 個情況而已。),但再乘上 C_3^4,就重複數算了。(注,乘上 C_3^4,就把原本僅出現一種花的 4 個情況,變成 16 個情況,重複了。)

P.S.

再想多想,如果我們用以下算法得 p_3

p_3 = N - p_1 - p_2

則,N = \frac{3^n + 3(2^n) - 10}{4^n},較「直觀但錯」的 C_3^4(\frac{3}{4})^n 複雜多,請問,它在數算什麼?

1 則迴響 »

  1. […] 以下為某中學授課員的網誌: https://johnmayhk.wordpress.com/2010/06/17/double-counting-example/ 借題發揮一下,我們來看看 a(iii) […]

    通告 由 391P Homework « 格仔人 (Checkered Man) — 2010/06/19 @ 1:44 上午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: