數數兒

數數兒

  1. Q: 2^A 有多少個元素?
    ==> 有多少種方法可以產生 2^A 的一個元素?
    ==> 要寫出一個元素, 可以分解成那幾個步驟?
    ==> 畫出一棵 decision tree, 數它的 leaves 個數. (因為每一條通往樹葉的路徑, 代表一種選法.)
    Ans: |2^A| = 2^|A|
  2. Q: 從 m 個相異球當中選出 n 個, 排入 n 個不同的位置, 有多少種排法?
    ==> 要產生出一種排法, 可以分解成那幾個步驟?
    ==> 畫出一棵 decision tree, 數它的 leaves 個數.
    Ans: P(m,n) = m!/(m-n)!
  3. Q: 從 m 個相異球當中選出 n 個, 有多少種選法?
    ==> 要產生出一種選法, 可以分解成那幾個步驟?
    ==> 畫出一棵 decision tree, 數它的 leaves 個數. ==> (觀察: 有好多不同的 leaves 其實都只能算作是同一種選法)
    ==> 挑一片樹葉來看, 數數看還有多少樹葉其實跟它都是相同的. (如何數? 又是另外一個數數兒的問題, 可以摹仿先前的作法...) Ans: C(m,n) = m!/(n!(m-n)!)
  4. C(m,n) 組合的數種意義:
    1. 從 m 個相異球當中選出 n 個, 有多少種選法?
    2. m 個元素的集合 A 的子集合當中, 有幾個內含 n 個元素?
    3. (1+x)^m 展開後, x^n 項係數是多少? (稱為 binomial coefficient)
    4. Pascal 三角形的第 m 列第 n 個值是多少?
    5. (「這究竟是一個排列的問題, 還是一個組合的問題?」) 把 n 個紅色的球, 與 m-n 個藍色的球排入 1 到 m 號共 m 個位置, 有多少種不同的排法?
  5. 結論: 不要按類型記公式, 因為記了太多公式也不一定知道一個題目要用那一個公式 -- 有些題目既可以當成排列, 也可以當成組合.
  6. m!/(k1!k2!...kt!) 的意義 (m = k1+k2...+kt):
    1. 有 k1 個紅球, k2 個藍球, ... kt 個白球 共 m 個球, 排入 1 到 m 號共 m 個位置, 有多少種不同的排法?
    2. 有 1 到 m 號共 m 個球, 其中要選 k1 個出來漆成紅色, 選 k2 個出來漆成藍色, ... 選 kt 個出來漆成白色, 共有多少種不同的選法?
    3. (r+b+...+w)^m 展開後, (r^k1)(b^k2)...(w^kt) 項係數是多少? (稱為 multinomial coefficient)
    (亦稱為「重複排列」)
  7. 結論: 不要按類型記公式! 要按照 "有多少種選/排法" ==> "如何選/排出一種結果" 的方式, 畫樹出來數 leaves!
  8. 例: 七男三女坐成一列, 共有多少種坐法? 若女士們一定要坐相連的位置, 有多少種坐法? 若要求男女間隔著坐, 且女士們不願意坐最兩側的位置, 有多少種坐法?
  9. 例: n 對夫妻圍著一個大圓桌坐下, 夫妻一定要坐在一起, 有多少種坐法?
  10. 全班有 60 人, 每 5 人分成一組. 共有多少種不同的分法?
  11. 金字塔模型的五面要塗上五種不同的顏色, 可用的顏色有七種, 共有多少種不同的塗色方法?
  12. 我的解題方法供參考:
    1. 題目問 "... 有多少種排/選法?"; 我問自己 "... 如何 有步驟, 有規律地 產生一種排/選法?" 然後用 principle of multiplication 把所有步驟的排/選法乘起來.
    2. 如果數重複了, 就挑一片樹葉 (一個結果) 起來看, 數數看還有多少其他樹葉 (其他結果) 其實跟它都是相同的. 如果當初的步驟選得好, 沒有製造出太多重複數的樹葉, 這半步就會變簡單, 例如多項式係數的另類想法: 視為好幾步的組合問題.
    3. 如果題目內有變數 (或數字太大) 不知道該如何數, 就先化簡題目, 用 4, 5 等小數字做一遍.
    以上方法已足以應付大部分簡單的排列組合題.
  13. 重複組合: 以下問題答案相同
    1. 有紅球無限多顆, 黃球無限多顆, ... 共 n 種顏色的球 (各無限多顆), 總共要選出 k 顆, 共有多少種選法?
    2. x1 + x2 + x3 ... + xn = k 有多少組非負整數解?
    3. k 個珠子排成一列, 之間要放入 n-1 個分隔板將它們分成 n 群, 分隔板有多少種放法?
  14. 例: x1+x2+x3+...+xn=k 的正整數解有多少個?
  15. Pigeonhole principle (鴿洞原理): 如果 n 隻鴿子要分配入 m 個鴿洞內, 且 m < n, 則至少有一個鴿洞內有兩隻或兩隻以上的鴿子.
  16. Extended pigeonhole principle: 若 n 隻鴿子要分配入 m 個鴿洞內, 則至少有一個鴿洞內有 ... 隻或更多的鴿子.