Quod Erat Demonstrandum

2012/02/16

Core Math 某題:數算 ABC

Filed under: NSS,Teaching — johnmayhk @ 8:58 上午

那天我代體育堂。一心期待上體育堂的 F.5C 學生,知我代堂,心情極度低落,課室之混亂可想而知,最重要是那時是午飯後的兩堂呀!我只隨意寫兩道題著他們想想。當然只有寥寥小貓理會。當中有學生反而問我以下問題:

Select 3 letters from a set {A,A,B,B,B,C,C}. How many different 3-letter ‘words’ can be formed? (e.g. AAB, CBA etc.)

學生給的答案是

\frac{P^7_3}{2!3!2!}

計出小數,明顯不對。學生問:為何?

先給一個解法,再化解學生的誤算。

考慮 3-letter word 可以出現的情況:

【情況 1】3 個字母相同,即只有 BBB 一個。

【情況 2】僅有 2 個字母相同,例如 ABA 者。考慮從 3 字母選 2 個,共 C^3_2=3 種。假如選了 A,B,也包括 {A,A,B} 和 {A,B,B} 2 種情況。對於 {A,A,B},可有 AAB,ABA,BAA 3 種排法。故【情況 2】共有 C^3_2\times 2\times 3=18 種。

【情況 3】3 個字母相異,即 ABC 者,共 3!=6 種。

故共有 1+18+6=25 個 3-letter words。(更快的方法,可參考 Comment 1)

至於出現

\frac{P^7_3}{2!3!2!}

應該是混淆了以下問題:

Number of ways of forming 7-leter words from {A,A,B,B,B,C,C} is \frac{P^7_7}{2!3!2!}.

\{A,A,B,B,B,C,C\} 看成 \{A_1,A_2,B_1,B_2,B_3,C_1,C_2\}

那麼 \{A_1,A_2,B_1,B_2,B_3,C_1,C_2\} 的 7 個不同的東西,就有 P^7_7 個排法。

但這 P^7_7 個排法中, 2!3!2! 個排法,其實是代表同一個 7-letter word。

比如 A_1A_2B_1B_2B_3C_1C_2 代表 AABBBCCA_2A_1B_3B_1B_2C_2C_1 也同樣代表 AABBBCC。考慮 A_1,A_22! 種排法,B_1,B_2,B_33! 種而 C_1,C_22! 種,所以 A_aA_bB_cB_dB_eC_fC_g2!3!2! 種排法,亦即 2!3!2! 個排法,其實是代表同一個 7-letter word。所以 7-letter words 只有 \frac{P^7_7}{2!3!2!} 個。

現在,在 \{A,A,B,B,B,C,C\} 選 3 個字母做 3-letter words,用同樣想法,可以考慮 \{A_1,A_2,B_1,B_2,B_3,C_1,C_2\}。不錯,可有 P^7_3 種排法,但這 P^7_3 種排法中,是否同樣地, 2!3!2! 個排法,代表同一個 3-letter word?不是。

比如

B_1B_2B_3
B_1B_3B_1
B_2B_1B_3
B_2B_3B_1
B_3B_1B_2
B_3B_2B_1

3! 種排法代表 BBB 這個 3-letter word。

A_1C_1A_2
A_1C_2A_2
A_2C_1A_1
A_2C_2A_1

2!2! 種排法代表 ACA。

A_1B_1A_2
A_2B_1A_1
A_1B_2A_2
A_2B_2A_1
A_1B_3A_2
A_2B_3A_1

卻有 2!3 種排法代表 ABA。

可見,並非「 2!3!2! 個排法,代表同一個 3-letter word」,亦即 3-letter words 並非 \frac{P^7_3}{2!3!2!} 個。

2 則迴響 »

  1. 教core來說,也許3^3-2=25簡單一點.

    迴響 由 Charlie — 2012/02/16 @ 2:31 下午 | 回覆

    • 減了 AAA 和 CCC,果然是好方法。謝!

      迴響 由 johnmayhk — 2012/02/16 @ 3:54 下午 | 回覆


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