108 年 國立成功大學電機工程學系碩士班丁組《離散數學》

核心觀念

1. 偏序集（Partially Ordered Set, Poset）定義：
   設 $S$ 為一非空集合，$\preceq$ 為定義在 $S$ 上的二元關係（Binary Relation）。若 $\preceq$ 同時滿足以下三個條件，則稱 $(S, \preceq)$ 為一偏序集：

   • 自反性（Reflexivity）：對所有 $a \in S$，$a \preceq a$。
   • 反對稱性（Antisymmetry）：對所有 $a, b \in S$，若 $a \preceq b$ 且 $b \preceq a$，則 $a = b$。
   • 遞移性（Transitivity）：對所有 $a, b, c \in S$，若 $a \preceq b$ 且 $b \preceq c$，則 $a \preceq c$。

2. 積序（Product Order / Componentwise Order）：
   在笛卡兒積空間 $A^3 = A \times A \times A$ 上，兩元素 $a = (a_1, a_2, a_3)$ 與 $b = (b_1, b_2, b_3)$ 的偏序關係 $\preceq$ 定義為「各分量皆滿足小於等於關係」：
   $a \preceq b \iff a_i \le b_i \quad \forall 1 \le i \le 3$

3. 哈斯圖（Hasse Diagram）：
   用以視覺化有限偏序集的簡化有向圖。繪製原則如下：

   • 分層繪製：若 $a \prec b$，則 $b$ 繪製於 $a$ 的上方。
   • 僅畫覆蓋關係（Covering Relation）：若 $a \prec b$ 且不存在 $c$ 使得 $a \prec c \prec b$，稱 $b$ 覆蓋（Cover）$a$（記作 $a \lessdot b$），此時在 $a$ 與 $b$ 之間畫一條連線。
   • 省略自環與遞移邊：不畫元素到自身的連線（由自反性隱含），亦不畫可由其他邊遞移到達的連線（由遞移性隱含）。

---

解題方法

(a) 證明 $(A^3, \preceq)$ 為偏序集

給定 $A = \{0, 1\}$，則 $A^3 = \{ (a_1, a_2, a_3) \mid a_1, a_2, a_3 \in \{0, 1\} \}$。關係 $\preceq$ 定義為 $a \preceq b \iff a_i \le b_i \; (\forall 1 \le i \le 3)$。

Step 1: 證明自反性（Reflexivity）
對於任意 $a = (a_1, a_2, a_3) \in A^3$：
因為 $a_i \in \{0, 1\}$，由實數標準小於等於關係 $\le$ 的自反性可知，$a_1 \le a_1$、$a_2 \le a_2$ 且 $a_3 \le a_3$。
根據 $\preceq$ 的定義，即有 $a \preceq a$。
故二元關係 $\preceq$ 滿足自反性。

Step 2: 證明反對稱性（Antisymmetry）
設任意 $a = (a_1, a_2, a_3), b = (b_1, b_2, b_3) \in A^3$ 滿足 $a \preceq b$ 且 $b \preceq a$：

• 由 $a \preceq b$ 可得 $a_1 \le b_1$、$a_2 \le b_2$、$a_3 \le b_3$。
• 由 $b \preceq a$ 可得 $b_1 \le a_1$、$b_2 \le a_2$、$b_3 \le a_3$。

因為標準小於等於關係 $\le$ 在 $\{0, 1\}$ 上具備反對稱性：
$a_i \le b_i$ 且 $b_i \le a_i \implies a_i = b_i \quad (\forall 1 \le i \le 3)$
因此 $a_1 = b_1$、$a_2 = b_2$ 且 $a_3 = b_3$，可得 $a = (a_1, a_2, a_3) = (b_1, b_2, b_3) = b$。
故二元關係 $\preceq$ 滿足反對稱性。

Step 3: 證明遞移性（Transitivity）
設任意 $a = (a_1, a_2, a_3), b = (b_1, b_2, b_3), c = (c_1, c_2, c_3) \in A^3$ 滿足 $a \preceq b$ 且 $b \preceq c$：

• 由 $a \preceq b$ 可得 $a_i \le b_i \quad (\forall 1 \le i \le 3)$。
• 由 $b \preceq c$ 可得 $b_i \le c_i \quad (\forall 1 \le i \le 3)$。

因為標準小於等於關係 $\le$ 在 $\{0, 1\}$ 上具備遞移性：
$a_i \le b_i$ 且 $b_i \le c_i \implies a_i \le c_i \quad (\forall 1 \le i \le 3)$
根據 $\preceq$ 的定義，可得 $a \preceq c$。
故二元關係 $\preceq$ 滿足遞移性。

結論：由於 $\preceq$ 滿足自反性、反對稱性與遞移性，$(A^3, \preceq)$ 為一偏序集（Poset）。

---

核心觀念

本題考查**二元關係（Binary Relation）**的核心性質：自反性（Reflexivity）、對稱性（Symmetry）、**遞移性（Transitivity）以及等價關係（Equivalence Relation）**的定義與聯集運算。

1. 關係性質之定義：設 $R$ 為集合 $X$ 上的二元關係。
   • 自反性（Reflexivity）：對所有 $a \in X$，均滿足 $(a, a) \in R$。
   • 對稱性（Symmetry）：若 $(a, b) \in R$，則必定 $(b, a) \in R$。
   • 遞移性（Transitivity）：若 $(a, b) \in R$ 且 $(b, c) \in R$，則必定 $(a, c) \in R$。
2. 等價關係（Equivalence Relation）：若關係 $R$ 同時滿足自反性、對稱性與遞移性，則稱 $R$ 為 $X$ 上的等價關係。
3. 關係的聯集（Union of Relations）：設 $R, S$ 為 $X$ 上的關係，$R \cup S = \{(a, b) \mid (a, b) \in R \text{ 或 } (a, b) \in S\}$。

---

解題方法

本題為是非判斷與證明題，解題策略如下：

1. 判斷真偽（True or False）：審視題目敘述的前提條件是否足以保證結論成立。若成立需給出一般性的嚴密證明；若不成立，只需舉出一組具體的**反例（Counterexample）**即可證明其為假。
2. (a) 小題切入點：欲從對稱性與遞移性推導自反性，常見謬誤為預設「對任意 $a \in X$，都存在某個 $b \in X$ 使得 $(a, b) \in R$」。若集合 $X$ 中存在未與任何元素產生關係的孤立元素，則自反性即宣告不成立。因此以包含孤立元素的集合構建反例。
3. (b) 小題切入點：兩等價關係的聯集必定維持自反性與對稱性，但遞移性在一般情況下不成立。若 $(x, y) \in R$ 且 $(y, z) \in S$，聯集 $R \cup S$ 雖包含 $(x, y)$ 與 $(y, z)$，但 $(x, z)$ 可能既不屬於 $R$ 亦不屬於 $S$，導致遞移性破壞。因此透過兩個不同的集合劃分（Partition）構造反例。

---

選項分析

(a) 小題：若關係 $R$ 同時具備對稱性與遞移性，則 $R$ 必為自反關係。

• 判斷：False（錯誤）
• 詳細分析與邏輯謬誤剖析：
  常見的盲點推導如下：假設 $(a, b) \in R$，由對稱性可知 $(b, a) \in R$；再由遞移性，結合 $(a, b) \in R$ 與 $(b, a) \in R$ 可推得 $(a, a) \in R$，因而誤認為 $R$ 必為自反關係。
  此推導的關鍵錯誤在於：自反性的定義要求對集合 $X$ 中「每一個」元素 $a \in X$，都必須滿足 $(a, a) \in R$。然而，前提並未保證任意 $a \in X$ 必定存在某個 $b \in X$ 使 $(a, b) \in R$。若存在元素 $a \in X$ 完全不參與關係 $R$，則 $(a, a) \notin R$。
• 反例說明：
  設集合 $X = \{1, 2, 3\}$。
  定義 $X$ 上的關係 $R = \{(1, 1), (1, 2), (2, 1), (2, 2)\}$。
  1. 對稱性檢驗：
     • $(1, 2) \in R \implies (2, 1) \in R$；$(1, 1), (2, 2)$ 倒轉後仍屬 $R$。故 $R$ 滿足對稱性。
  2. 遞移性檢驗：
     • $(1, 2) \in R \land (2, 1) \in R \implies (1, 1) \in R$。

核心觀念

本題的核心觀念為鴿籠原理（Pigeonhole Principle，又稱鴿巢原理或抽屜原理）與最壞情況分析（Worst-case Analysis / Extremal Principle）。

1. 鴿籠原理（Pigeonhole Principle）：
   若將 $m$ 隻鴿子放入 $n$ 個鴿籠中，且 $m > n$，則必定存在至少一個鴿籠裡面裝有 $2$ 隻或 $2$ 隻以上的鴿子。
2. 最壞情況分析（Worst-case Scenario）：
   題目要求「保證（be sure）」至少有兩個整數擁有共同數字。求解此類問題的關鍵切入點為：先計算在「完全沒有任何兩數共享數字」的情形下，最多能夠挑選出多少個整數（即構造最壞情況的反例極限），再將該數量加 $1$，即可得到確保必然發生重疊的最小挑選數量。
3. 三位數的數字結構限制：
   在介於 $100$ 至 $999$ 之間的整數中，每一個數均為三位數，其百位數字必屬於非零數字集合 $D_{\text{nonzero}} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$（共 $9$ 個非零數字）。數字 $0$ 雖然可出現在十位或個位，但無法獨立構成任何三位數。

---

解題方法

本題目標為求出最小的挑選整數個數 $m$，使得從 $100$ 到 $999$ 挑出的 $m$ 個整數中，必然存在至少兩個整數共享至少一個阿拉伯數字。

步驟一：分析可用數字資源與集合構造

十進位系統的數字集合為 $D = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$，共有 $10$ 個數字。
由於挑選範圍為 $100$ 至 $999$ 的三位數，任何一個被選出的整數 $x$，其百位數字必然屬於非零數字集合 $D_{\text{nonzero}} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$。這意味著每一個三位數都必定包含至少一個來自 $D_{\text{nonzero}}$ 的非零數字。

步驟二：建構「完全無共同數字」的最大整數集合（最壞情況）

若要讓挑出的整數之間盡可能「不共享任何數字」，每個整數應盡可能只消耗 $1$ 個數字。
考慮挑選以下 $9$ 個整數組成的集合：
$S = \{111, 222, 333, 444, 555, 666, 777, 888, 999\}$

檢查這 $9$ 個整數所使用的數字集合：

• $111$ 使用數字集合 $\{1\}$
• $222$ 使用數字集合 $\{2\}$
• $333$ 使用數字集合 $\{3\}$
• $444$ 使用數字集合 $\{4\}$
• $555$ 使用數字集合 $\{5\}$
• $666$ 使用數字集合 $\{6\}$
• $777$ 使用數字集合 $\{7\}$
• $888$ 使用數字集合 $\{8\}$
• $999$ 使用數字集合 $\{9\}$

這 $9$ 個整數所使用的數字集合兩兩交集皆為空集合 $\emptyset$，即任意兩數均無共同數字。

核心觀念

1. 普通生成函數（Ordinary Generating Function, OGF）：
   在組合數學中，若選取物件的順序無關（Order does not matter），計算非負整數解個數的問題通常使用普通生成函數（OGF）求解。若每一種物件可重複選取任意非負整數次，則可將各物件所能貢獻的數值以形式冪級數（Formal Power Series）表示後相乘。
2. 找零問題（Change-making Problem / Integer Partition）：
   若有面額為 $c_1, c_2, \dots, c_k$ 的代幣，投入個數分別為 $e_1, e_2, \dots, e_k \ge 0$，求滿足下列方程式的非負整數解組數：
   $c_1 e_1 + c_2 e_2 + \dots + c_k e_k = r$
   其對應的普通生成函數 $G(x)$ 為各面額單項生成函數的乘積，總金額 $r$ 元的組合數即為 $G(x)$ 中 $x^r$ 項的係數 $[x^r]G(x)$。

---

解題方法

1. 定義變數與方程式：
   設投入面額為 $1、$2 及 $5 的代幣數量分別為 $e_1, e_2, e_5$。
   依題意，代幣的選取不考慮順序（Order does NOT matter），因此求支付總額 $r$ 元的方法數，等價於求滿足下列限制式之非負整數解 $(e_1, e_2, e_5)$ 的個數：
   $1 \cdot e_1 + 2 \cdot e_2 + 5 \cdot e_5 = r, \quad e_1, e_2, e_5 \in \{0, 1, 2, 3, \dots\}$

2. 建立各面額代幣的生成函數因子：

   • $1 代幣：可投入 $0, 1, 2, 3, \dots$ 個，對應金額為 $0, 1, 2, 3, \dots$ 元：
     $1 + x^1 + x^2 + x^3 + \dots = \sum_{e_1=0}^{\infty} x^{e_1} = \frac{1}{1-x}$
   • $2 代幣：可投入 $0, 1, 2, 3, \dots$ 個，對應金額為 $0, 2, 4, 6, \dots$ 元：
     $1 + x^2 + x^4 + x^6 + \dots = \sum_{e_2=0}^{\infty} x^{2e_2} = \frac{1}{1-x^2}$

核心觀念

本題考查離散數學中的平面分割問題（Plane Division by Lines），屬於經典的遞迴關係式（Recurrence Relation）與階差數列求解範疇。核心觀念包含：

1. 一般位置（General Position）：若要使 $n$ 條直線在平面上切割出的區域數量達到最大值 $R_n$，任意兩條直線不得平行，且任意三條直線不得交於同一點（無三線共點）。
2. 遞迴構造思想：考慮加入第 $n$ 條直線時，該直線與前 $n-1$ 條直線相交，被 $n-1$ 個交點分割成 $n$ 個區段（含線段與射線）。每一個區段穿過一個原有的區域並將其一分為二，從而額外創造出 $n$ 個新區域。
3. 階差累加法（Telescoping Sum）：利用 $R_n - R_{n-1} = n$ 的階差特性，透過累加求和即可導出封閉型式（Closed Form）。

---

解題方法

(a) 求 $R_1, R_2, R_3, R_4$ 之值

• $R_0 = 1$：尚未畫出任何直線時，整個平面本身即為 $1$ 個完整區域。
• $R_1 = 2$：畫入 $1$ 條直線，將平面分割為 $2$ 個區域。
• $R_2 = 4$：畫入第 $2$ 條直線（與第 $1$ 條直線相交），新增 $2$ 個區域，$R_2 = 2 + 2 = 4$。
• $R_3 = 7$：畫入第 $3$ 條直線（與前 $2$ 條直線交於 $2$ 個不同點），第 $3$ 條直線被分割成 $3$ 個區段，新增 $3$ 個區域，$R_3 = 4 + 3 = 7$。
• $R_4 = 11$：畫入第 $4$ 條直線（與前 $3$ 條直線交於 $3$ 個不同點），第 $4$ 條直線被分割成 $4$ 個區段，新增 $4$ 個區域，$R_4 = 7 + 4 = 11$。

---

(b) 建立 $R_n$ 的遞迴關係式（Recurrence Equation）

設平面上已有 $n-1$ 條處於一般位置的直線，共有 $R_{n-1}$ 個區域。

當加入第 $n$ 條直線時：

1. 為使創造的區域數達到最大，第 $n$ 條直線必須與前面的每一條直線（共 $n-1$ 條）皆相交且不共點，因此會產生 $n-1$ 個相異的交點。
2. 這 $n-1$ 個交點順序將第 $n$ 條直線切割成 $n$ 個區段（包括 $2$ 條無窮射線與 $n-2$ 個有限線段）。
3. 第 $n$ 條直線上的每一個區段，都會正好橫跨並切割原有的 $1$ 個區域，使其分裂為 $2$ 個新區域。
4. 因此，第 $n$ 條直線總共額外增加了 $n$ 個區域。

由此可得遞迴關係式與初始條件：
$R_n = R_{n-1} + n \quad (n \ge 1)$
初始條件為 $R_0 = 1$（或 $R_1 = 2$）。

---

(c) 求解 $R_n$ 的封閉型式（Closed Form）

將遞迴關係式寫成階差形式並依序展開：
$R_n - R_{n-1} = n$
$R_{n-1} - R_{n-2} = n-1$
$\vdots$
$R_2 - R_1 = 2$
$R_1 - R_0 = 1$

核心觀念

本題考查機率論（Probability Theory）中的兩個核心定理：

1. 全機率定理（Law of Total Probability）：當樣本空間劃分為若干互斥事件時，欲求某一目標事件發生的總機率，可將該目標事件在各劃分事件下的條件機率乘以各劃分事件本身的先驗機率後進行累加。
2. 貝氏定理（Bayes' Theorem）：用於在已知結果（條件）發生的前提下，反推該結果是由特定原因（互斥事件之一）所產生的後驗機率（Posterior Probability）。

---

解題方法

1. 事件定義與已知條件

• 設 $U_1$ 為選擇「第一個籃子（Urn 1）」的事件。
• 設 $U_2$ 為選擇「第二個籃子（Urn 2）」的事件。
• 設 $G$ 為取出的球為「綠球（Green Ball）」的事件。

根據題目敘述：

• 擲硬幣選籃子（正面選第一籃，反面選第二籃）：
  $P(U_1) = 0.4 = \frac{2}{5}$
  $P(U_2) = 0.6 = \frac{3}{5}$

• 第一個籃子含有 10 顆紅球、25 顆綠球，總球數為 $10 + 25 = 35$ 顆：
  $P(G \mid U_1) = \frac{25}{35} = \frac{5}{7}$

• 第二個籃子含有 22 顆紅球、15 顆綠球，總球數為 $22 + 15 = 37$ 顆：
  $P(G \mid U_2) = \frac{15}{37}$

---

2. 推導與計算步驟

(a) 計算取出的球為綠球的機率 $P(G)$

利用全機率定理展開：
$P(G) = P(U_1) \cdot P(G \mid U_1) + P(U_2) \cdot P(G \mid U_2)$

代入數值進行推導：
$P(G) = \left(\frac{2}{5} \times \frac{5}{7}\right) + \left(\frac{3}{5} \times \frac{15}{37}\right)$
$P(G) = \frac{2}{7} + \frac{45}{185} = \frac{2}{7} + \frac{9}{37}$

通分計算：
$P(G) = \frac{2 \times 37 + 9 \times 7}{7 \times 37} = \frac{74 + 63}{259} = \frac{137}{259}$

---

(b) 若已知取出的球為綠球，求該球來自第一個籃子的機率 $P(U_1 \mid G)$

利用貝氏定理展開：
$P(U_1 \mid G) = \frac{P(U_1 \cap G)}{P(G)} = \frac{P(U_1) \cdot P(G \mid U_1)}{P(G)}$

代入分子（第一籃且取到綠球的機率）與分母（(a) 小題求出的總綠球機率）：
$P(U_1 \cap G) = \frac{2}{5} \times \frac{5}{7} = \frac{2}{7}$

核心觀念

本題屬於離散數學中**組合數學（Combinatorics）**的經典考題，核心考點包含以下兩大觀念：

1. 重複組合（Combinations with Repetition / Multiset Coefficients）：
   將 $n$ 種相異物品中選取 $r$ 個物品的組合數（允許重複選取且不計順序），記為 $H_r^n$ 或 $H(n, r)$，其計算公式為：
   $H(n, r) = \binom{n + r - 1}{r} = \binom{n + r - 1}{n - 1}$
   在數學建模上，這等價於求不定方程式 $x_1 + x_2 + \dots + x_n = r$ 的非負整數解個數（其中 $x_i \ge 0$）。

2. 排容原理（Inclusion-Exclusion Principle, IEP）：
   當變數設有限制條件（例如上限限制 $x_i \le m$）時，直接計算較為困難。此時可先計算無上限限制下的總解數，再透過排容原理扣除違反限制條件（即 $x_i \ge m+1$）的不合情況：
   $|A_1' \cap A_2'| = |S| - |A_1| - |A_2| + |A_1 \cap A_2|$

---

解題方法

步驟一：建立數學模型（不定方程式）

設購買 8 種氣球的數量分別為 $x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8$。
根據題意，總共需選取 30 個氣球，且各氣球庫存限制如下：

• 紅氣球（設為 $x_1$）：只有 12 個 $\implies 0 \le x_1 \le 12$
• 藍氣球（設為 $x_2$）：只有 8 個 $\implies 0 \le x_2 \le 8$
• 其餘 6 種氣球（$x_3 \sim x_8$）：至少各有 30 個 $\implies x_i \ge 0$（因為總選取數僅為 30，庫存超出一可能最大需求，故無上限限制）

目標為求不定方程式：
$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 = 30$
在限制條件下的非負整數解個數。

---

步驟二：使用「排容原理」推導與計算

1. 求全集 $S$ 的解數（不考慮上限限制，僅考慮 $x_i \ge 0$）：
$|S| = H(8, 30) = \binom{8 + 30 - 1}{30} = \binom{37}{30} = \binom{37}{7}$

2. 定義不合條件的屬性（違反上限）：

• 屬性 $A_1$：紅氣球選取過多，即 $x_1 \ge 13$。
• 屬性 $A_2$：藍氣球選取過多，即 $x_2 \ge 9$。

3. 計算各不合集合的大小：

• 計算 $|A_1|$（$x_1 \ge 13$）：
  令 $x_1' = x_1 - 13 \ge 0$，原式化為：
  $x_1' + x_2 + x_3 + \dots + x_8 = 30 - 13 = 17$
  解數為 $|A_1| = H(8, 17) = \binom{8 + 17 - 1}{17} = \binom{24}{17} = \binom{24}{7}$

• 計算 $|A_2|$（$x_2 \ge 9$）：
  令 $x_2' = x_2 - 9 \ge 0$，原式化為：
  $x_1 + x_2' + x_3 + \dots + x_8 = 30 - 9 = 21$
  解數為 $|A_2| = H(8, 21) = \binom{8 + 21 - 1}{21} = \binom{28}{21} = \binom{28}{7}$

• 計算 $|A_1 \cap A_2|$（$x_1 \ge 13$ 且 $x_2 \ge 9$）：
  令 $x_1' = x_1 - 13 \ge 0$ 且 $x_2' = x_2 - 9 \ge 0$，原式化為：
  $x_1' + x_2' + x_3 + \dots + x_8 = 30 - 13 - 9 = 8$
  解數為 $|A_1 \cap A_2| = H(8, 8) = \binom{8 + 8 - 1}{8} = \binom{15}{8} = \binom{15}{7}$

4. 套用排容原理計算符合條件的解數：
$\text{所求組合數} = |S| - |A_1| - |A_2| + |A_1 \cap A_2| = \binom{37}{7} - \binom{28}{7} - \binom{24}{7} + \binom{15}{7}$

---

步驟三：組合數數值展開