🔢 離散數學 - 計數原理重點複習 🔢

⚡ 快速記憶口訣

1. 基本計數原理 (Basic Counting Principles)

📌 乘法原理 (Multiplication Principle)

如果一件事要分多個步驟完成，第一步有 m 種方法，第二步有 n 種方法，則總共有 m × n 種方法。

第一步
m 種選擇
→
第二步
n 種選擇
=
總共
m × n 種
範例：密碼設定

設定4位數密碼，每位可選0-9：

每個位置都有10種選擇
總數 = 10 × 10 × 10 × 10 = 10,000 種

📌 加法原理 (Addition Principle)

如果一件事可以用多種互斥方式之一完成，第一種有 m 種方法，第二種有 n 種方法，則總共有 m + n 種方法。

範例：選修課程

可以選3門數學課之一或5門物理課之一：

總選擇 = 3 + 5 = 8 種

2. 排列 (Permutation)

重點：考慮順序！ AB 和 BA 是不同的排列。

公式： P(n,r) = n!/(n-r)! = n × (n-1) × ... × (n-r+1)
從 n 個不同元素中取 r 個排列

例：從 ABC 中選 2 個排列

AB
AC
BA
BC
CA
CB

共 P(3,2) = 3!/(3-2)! = 6 種

範例：選幹部

25人中選出會長、副會長、秘書（一人一職）：

P(25,3) = 25 × 24 × 23 = 13,800 種
記憶方式：第一個位置有 n 種選擇，第二個有 n-1 種，依此類推。

3. 組合 (Combination)

重點：不考慮順序！ AB 和 BA 是相同的組合。

公式： C(n,r) = n!/(r!(n-r)!) = P(n,r)/r!
從 n 個不同元素中選 r 個組合
又記作：nCr 或 (n choose r)

例：從 ABC 中選 2 個組合

{A,B}
{A,C}
{B,C}

共 C(3,2) = 3!/(2!1!) = 3 種

範例：選委員會

25人中選4人組成委員會：

C(25,4) = 25!/(4!×21!) = 12,650 種

4. 重要公式一覽表

情況 公式 說明 範例
排列（無重複） P(n,r) = n!/(n-r)! n個選r個，有序 選班級幹部
組合（無重複） C(n,r) = n!/(r!(n-r)!) n個選r個，無序 選委員會成員
重複排列 n^r n個選r個，可重複，有序 密碼（可重複數字）
重複組合 C(n+r-1, r) n個選r個，可重複，無序 買水果（同種可買多個）
全排列 n! n個全部排列 n本書排成一列

5. 特殊計數技巧

🔄 補集原理 (Complement Principle)

至少一個 = 總數 - 一個都沒有
範例：至少包含一個@

5個字元的字串，每個位置有128種選擇，至少包含一個@：

總數 - 都不含@ = 128^5 - 127^5

🔀 容斥原理 (Inclusion-Exclusion)

|A∪B| = |A| + |B| - |A∩B|
範例：以000開頭或以00結尾

10位元字串：

A = 以000開頭：2^7 = 128
B = 以00結尾：2^8 = 256
A∩B = 以000開頭且以00結尾：2^5 = 32
答案 = 128 + 256 - 32 = 352

🕊️ 鴿籠原理 (Pigeonhole Principle)

如果 n+1 個物品放入 n 個箱子，至少有一個箱子包含超過一個物品。

範例：同色襪子

抽屜有12雙棕色襪子和12雙黑色襪子，要確保有一雙同色：

最壞情況：先拿1隻棕色、1隻黑色
第3隻必定與前兩隻之一同色
答案：3隻

6. 球與箱問題 (Balls and Bins)

📦 隔板法 (Stars and Bars)

將 n 個相同物品分配到 k 個不同箱子：

C(n+k-1, k-1) 種方法

例：5個相同球放入3個不同箱子

●●●●● 用2個隔板分成3組：●●|●●|●

相當於排列5個●和2個|的方法

球 箱子 限制 公式
相同 不同 無限制 C(n+k-1, k-1)
相同 不同 每箱至少1個 C(n-1, k-1)
不同 不同 無限制 k^n
不同 不同 每箱至多1個 P(k,n) = k!/(k-n)!

7. 二項式定理 (Binomial Theorem)

(x + y)^n = Σ C(n,k) × x^k × y^(n-k)
其中 k 從 0 到 n
範例：展開項數

(x + y)^100 展開後有幾項？

k 可以是 0, 1, 2, ..., 100
共 101 項
範例：特定項係數

(2x - 3y)^5 中 x^3y^2 的係數？

使用 k = 3：C(5,3) × (2)^3 × (-3)^2
= 10 × 8 × 9 = 720

8. 常見題型與解法

🎯 解題步驟

  1. 判斷有序/無序：順序重要嗎？
  2. 判斷重複：可以重複選擇嗎？
  3. 找出限制條件：至少、至多、恰好？
  4. 選擇方法：直接計算或使用補集？
關鍵詞 英文 解法提示
至少一個 at least one 用補集：總數 - 一個都沒有
恰好 exactly 直接用組合計算
至多 at most 加總0到n的情況
位元字串 bit string 每位2種選擇（0或1）
一對一函數 one-to-one function 用排列（不能重複對應）
包含字串 contain string 當作一個單位處理

📝 考前必背公式卡

💪 加油！相信你一定可以考好的！

記住：多練習題目，熟能生巧！