Quod Erat Demonstrandum

2007/12/13

[AL][PM][AM] 以應數技巧解純數中涉及 nCr 的問題

Filed under: Additional / Applied Mathematics,HKALE,Pure Mathematics,Teaching — johnmayhk @ 4:07 下午

在我還是中學生的年代,初等的組合問題在應數及純數科也有涉獵。現在,我們只能在應數科看到,於是只修讀純數的同學,相信必循 C_{r}^{n} 的『定義』出發,解以下問題。

證明

1. C_{r+1}^{n+1} = C_{r}^{n} + C_{r+1}^{n}
2. C_{r}^{m + n} = \sum_{k=0}^{r}C_{r-k}^{m}C_{k}^{n} (r \leq \min (m , n))
3. C_{n+1}^{m+n+1} = \sum_{k=n}^{n+m}C_{n}^{k} (即 1994 年 Paper I Q.7)

讓我以非純數的方式處理。

Q.1 堂上我已提及,由柏斯卡三角的構作方式,已體現了它。再給一法:

在 n + 1 個人中選出 r +1 個,有多少組合方式?答曰:C_{r + 1}^{n + 1}
假設阿 John 是 n + 1 人中的其中一個,那麼,要選出 r + 1 人,我們可以有兩種情況:選阿 John 及不選阿 John。
如果要選阿 John,則我們還要在其他的 n 個人中選出 r 個,組合方式共 C_{r}^{n} 種。
如果不選阿 John,則我們要在其他的 n 個人中選出 r + 1 個,組合方式共 C_{r + 1}^{n} 種。
故在 n + 1 人中選出 r + 1 個的組合方式共 C_{r}^{n} + C_{r + 1}^{n} 種,所以有 C_{r+1}^{n+1} = C_{r}^{n} + C_{r+1}^{n}。清脆利落。

Q.2 C_{r}^{m + n} 就是在 m + n 人中選出 r 個的組合方式之數目。現在考慮 m + n 人內有 m 男 n 女。於是,要選出 r 人,可以是

r 男 0 女,共 C_{r}^{m} \times C_{0}^{n} 種組合,或
r – 1 男 1 女,共 C_{r - 1}^{m} \times C_{1}^{n} 種組合,或
r – 2 男 2 女,共 C_{r - 2}^{m} \times C_{2}^{n} 種組合,或

0 男 r 女,共 C_{0}^{m} \times C_{r}^{n} 種組合。

於是,在 m + n 人中選出 r 個的組合方式數目,就是上述各組合方式之總和,亦即 C_{r}^{m + n} = \sum_{k=0}^{r}C_{r-k}^{m}C_{k}^{n}

Q.3 在純數課中,我們可以考慮 (1+x)^n + (1+x)^{n+1} + ... + (1+x)^{m+n+1} 及 G.P. sum 便可解之。但我們也可用應數中的『概率』解之如下:

考慮正整數 1,2,3,…,m + n + 1。
我們從這 m + n + 1 個數字隨意取 n + 1 個。
設 P(k) = 這 n + 1 個數字中,最大者為 k + 1 的概率。

嗯,幫幫同學,舉實例。比如在 1 至 30 中,任取 10 個數,問 P(19)。即這 10 個數,最大的一個是 20,那麼其餘的 9 個,就要在 {1,2,3,…,19} 中選取,我們才有『最大的一個是 20』這個效果,即 P(19) = \frac{C_{9}^{19}}{C_{10}^{30}}

以同樣想法,我們不難得到 P(k) = \frac{C_{n}^{k}}{C_{n + 1}^{m + n + 1}} (n \leq k)。那麼,考慮最大數的『所有可能性』,即 k = n , n + 1 , n + 2 , … , m + n,有

P(n) + P(n + 1) + P(n + 2) + … + P(n + m) = 1

立即推出 C_{n+1}^{m+n+1} = \sum_{k=n}^{n+m}C_{n}^{k}

純數應數如何分?嗯,數學本一家嘛。

1 則迴響 »

  1. […] read Like this:LikeBe the first to like this post. Leave a […]

    通告 由 簡單算數 « Quod Erat Demonstrandum — 2011/12/21 @ 6:16 上午 | 回覆


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 位部落客按了讚: