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

核心觀念

本題旨在考驗離散數學與機率論中的核心觀念：

1. 事件的獨立性（Independence of Events）：
   若事件 $A$ 與 $B$ 獨立，則其同時發生的機率滿足乘法定理：
   $P(A \cap B) = P(A) \cdot P(B)$
   同理，其補集事件對 $(A^c, B)$、$A, B^c$ 及 $(A^c, B^c)$ 亦皆相互獨立。
2. 德摩根定律（De Morgan's Laws）與集合表達：
   • 「事件 $A$ 與 $B$ 皆未發生」定義為事件 $C = A^c \cap B^c = (A \cup B)^c$。
   • 「事件 $A$ 與 $B$ 恰有一者發生」定義為事件 $D = (A \cap B^c) \cup (A^c \cap B) = (A \cup B) \setminus (A \cap B)$。
3. 排容原理（Inclusion-Exclusion Principle）：
   $P(A \cup B) = P(A) + P(B) - P(A \cap B)$
4. 條件機率（Conditional Probability）：
   給定事件 $D$ 發生的條件下，事件 $A$ 發生的條件機率定義為：
   $P(A | D) = \frac{P(A \cap D)}{P(D)} \quad (\text{其中 } P(D) > 0)$

---

解題方法

根據題意，已知 $P(A) = 0.2$、$P(B) = 0.3$，且 $A$ 與 $B$ 為獨立事件。

第一步先求出兩者同時發生的交集機率：
$P(A \cap B) = P(A) \cdot P(B) = 0.2 \times 0.3 = 0.06$

據此展開各小題的運算推導：

(a) 求 $P(C)$

事件 $C$ 代表 $A$ 與 $B$ 皆未發生，即 $C = (A \cup B)^c$。

• 方法一（排容原理與補集機率）：
  先計算聯集機率 $P(A \cup B)$：
  $P(A \cup B) = P(A) + P(B) - P(A \cap B) = 0.2 + 0.3 - 0.06 = 0.44$
  因此 $C$ 的機率為：
  $P(C) = 1 - P(A \cup B) = 1 - 0.44 = 0.56$

• 方法二（獨立事件性質）：
  因 $A$ 與 $B$ 獨立，故 $A^c$ 與 $B^c$ 亦相互獨立：
  $P(C) = P(A^c \cap B^c) = P(A^c) \cdot P(B^c) = (1 - 0.2) \times (1 - 0.3) = 0.8 \times 0.7 = 0.56$

(b) 求 $P(D)$

事件 $D$ 代表 $A$ 與 $B$ 中恰有一者發生，即 $D = (A \cap B^c) \cup (A^c \cap B)$。
由於 $(A \cap B^c)$ 與 $(A^c \cap B)$ 為互斥事件（Mutually Exclusive Events），機率可直接相加：
$P(D) = P(A \cap B^c) + P(A^c \cap B)$
運用獨立性求個別機率：
$P(A \cap B^c) = P(A) \cdot P(B^c) = 0.2 \times (1 - 0.3) = 0.14$
$P(A^c \cap B) = P(A^c) \cdot P(B) = (1 - 0.2) \times 0.3 = 0.24$
故：
$P(D) = 0.14 + 0.24 = 0.38$

核心觀念

本題考查離散數學中**二元關係（Binary Relations）與等價關係（Equivalence Relations）的基本定義、性質證明及等價類（Equivalence Classes）**的求法：

1. 整除與奇偶性：在整數集 $S = \mathbb{Z}$ 上定義二元關係 $\sim$，其中 $x \sim y \iff 2 \mid (x+y)$。此條件代表 $x+y$ 為偶數，即 $x$ 與 $y$ 具有相同的奇偶性（同為偶數或同為奇數）。
2. 等價關係（Equivalence Relation）的判定：集合 $S$ 上的二元關係 $\sim$ 為等價關係，若且唯若其同時滿足以下三項基本性質：
   • 自反性（Reflexivity）：對所有 $x \in S$，皆有 $x \sim x$。
   • 對稱性（Symmetry）：對所有 $x, y \in S$，若 $x \sim y$，則 $y \sim x$。
   • 遞移性（Transitivity）：對所有 $x, y, z \in S$，若 $x \sim y$ 且 $y \sim z$，則 $x \sim z$。
3. 等價類（Equivalence Class）與劃分（Partition）：元素 $x \in S$ 所屬的等價類記做 $[x]$，定義為包含所有與 $x$ 具備關係 $\sim$ 的元素集合：
   $[x] = \{ y \in S \mid x \sim y \}$
   等價關係會將全域集合 $S$ 唯一劃分成若干個互斥且相聯集的等價類集合。

---

解題方法與推導

題目給定集合 $S = \mathbb{Z}$，關係定義為 $x \sim y \iff 2 \mid (x+y)$。

(a) 列出六個與 $x=2$ 相關的數字

根據關係定義，尋找滿足 $2 \sim y$ 的整數 $y$：
$2 \sim y \iff 2 \mid (2+y)$
因為 $2+y$ 必須被 $2$ 整除（即 $2+y$ 為偶數），而 $2$ 本身即為偶數，故 $y$ 必須為偶數。
凡為整數中的偶數，皆滿足與 $x=2$ 有關係。

挑選任意六個相異偶數即可，例如：
$0, 4, 6, 8, 10, 12$

---

(b) 證明 $\sim$ 為集合 $S$ 上的等價關係

須依序驗證自反性、對稱性與遞移性：

1. 自反性（Reflexivity）：
   對任意整數 $x \in \mathbb{Z}$，考慮 $x+x$：
   $x + x = 2x$
   因為 $x \in \mathbb{Z}$，故 $2x$ 必然能被 $2$ 整除，即 $2 \mid (x+x)$。
   得證對所有 $x \in \mathbb{Z}$，皆有 $x \sim x$。

2. 對稱性（Symmetry）：
   對任意整數 $x, y \in \mathbb{Z}$，假設 $x \sim y$。
   由定義可得 $2 \mid (x+y)$，即存在整數 $k \in \mathbb{Z}$ 使得 $x+y = 2k$。
   根據整數加法的交換律：
   $y+x = x+y = 2k$
   因此 $2 \mid (y+x)$，推得 $y \sim x$。
   得證 $\sim$ 滿足對稱性。

核心觀念

本題考查離散數學與機率論中「離散隨機變數」與「期望值（Expected Value）」的計算，核心工具為指示隨機變數（Indicator Random Variable）與期望值的線性性質（Linearity of Expectation）。

1. 指示隨機變數（Indicator Random Variable）：
   若事件 $A$ 發生，則指示隨機變數 $I_A = 1$；否則 $I_A = 0$。其期望值等於該事件發生的機率：
   $E[I_A] = 1 \times P(A) + 0 \times P(A^c) = P(A)$

2. 期望值的線性性質（Linearity of Expectation）：
   對任意隨機變數 $X_1, X_2, \dots, X_n$（無論彼此是否獨立），其和的期望值等於各隨機變數期望值的和：
   $E[X_1 + X_2 + \dots + X_n] = E[X_1] + E[X_2] + \dots + E[X_n]$

3. 鴿籠原理（Pigeonhole Principle）：
   三角形的 3 個頂點僅塗上 2 種顏色，必然至少有 2 個頂點同色，因此兩端點同色的邊數不可能為 0。

---

解題方法

方法一：指示隨機變數法（最簡捷推導）

1. 定義隨機變數：
   設三角形的 3 條邊分別為 $e_1, e_2, e_3$。
   對每條邊 $e_i$（$i = 1, 2, 3$），定義指示隨機變數 $X_i$ 如下：
   $X_i = \begin{cases} 1, & \text{若邊 } e_i \text{ 的兩個端點顏色相同} \\ 0, & \text{若邊 } e_i \text{ 的兩個端點顏色不同} \end{cases}$
   則三角形中「兩端點同色的邊數」隨機變數為 $X = X_1 + X_2 + X_3$。

2. 計算單一邊端點同色的機率與期望值：
   對任意一條邊 $e_i = (u, v)$，端點 $u$ 與 $v$ 的塗色結果共有 4 種等機率組合：$(\text{黑}, \text{黑})$、$(\text{黑}, \text{白})$、$(\text{白}, \text{黑})$、$(\text{白}, \text{白})$。
   其中端點顏色相同的組合有 $(\text{黑}, \text{黑})$ 與 $(\text{白}, \text{白})$ 兩種，故：
   $P(X_i = 1) = \left(\frac{1}{2} \times \frac{1}{2}\right) + \left(\frac{1}{2} \times \frac{1}{2}\right) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$
   因此，$X_i$ 的期望值為：
   $E[X_i] = P(X_i = 1) = \frac{1}{2}$

3. 利用期望值線性性質求總期望值：
   $E[X] = E[X_1 + X_2 + X_3] = E[X_1] + E[X_2] + E[X_3] = \frac{1}{2} + \frac{1}{2} + \frac{1}{2} = \frac{3}{2}$

方法二：樣本空間完全列舉法（驗算用）

1. 建立樣本空間：
   設三角形頂點為 $v_1, v_2, v_3$，塗色結果以三元組 $(v_1, v_2, v_3)$ 表示。

【觀念剖析】
關係 $R$ 的遞移閉包 (Transitive Closure) 定義為 $\hat{R} = \bigcup_{k=1}^{\infty} R^k$。
本題要求的條件：

1. $\hat{R} = R \cup R^2 \cup R^3$：代表關係的反覆複合在長度 3 以內即可達到閉包（即長度 4 以上的複合不會產生新的元素對）。
2. $R \neq R \cup R^2$：代表 $R$ 本身不是遞移關係（Transitive），即存在 $R^2$ 含有不屬於 $R$ 的新元素對。

【範例構造與驗證】
考慮集合 $A = \{1, 2, 3, 4\}$，定義關係 $R$ 為：
$R = \{(1, 2), (2, 3), (3, 4)\}$

1. 計算 $R^2$：
   $R^2 = R \circ R = \{(1, 3), (2, 4)\}$

【重點觀念】

• 數學歸納法 (Mathematical Induction)：對於所有正整數 $n$，證明等式 $P(n)$ 成立。
• 費氏數列遞迴定義：$f_k = f_{k+1} - f_{k-1}$ （即 $f_{k-1} + f_k = f_{k+1}$）。

---

【詳細證明】

設命題 $P(n)$ 為：
$f_0 f_1 + f_1 f_2 + f_2 f_3 + \dots + f_{2n-1} f_{2n} = f_{2n}^2$

1. 基礎步驟 (Base Step)：
當 $n = 1$ 時：

• 左式 $= f_0 f_1 + f_1 f_2 = 0 \cdot 1 + 1 \cdot 1 = 1$
• 右式 $= f_2^2 = (f_0 + f_1)^2 = (0 + 1)^2 = 1$
  左式 $=$ 右式，故 $P(1)$ 成立。

2. 歸納假設 (Induction Hypothesis)：
假設當 $n = k$ ($k \ge 1$) 時命題 $P(k)$ 成立，即：
$f_0 f_1 + f_1 f_2 + \dots + f_{2k-1} f_{2k} = f_{2k}^2$

3. 歸納步驟 (Induction Step)：

核心觀念

本題為經典的離散數學綜合考題，核心涵蓋以下三個重點觀念：

1. 非負整數解個數（重複組合，Combination with Repetition）：
   方程式 $x_1 + x_2 + \dots + x_n = k$ 的非負整數解個數，可以表示為重複組合 $H^n_k = \binom{n + k - 1}{k}$。
2. 排容原理（Inclusion-Exclusion Principle）：
   對於任意兩個事件 $E_1$ 與 $E_2$，其交集與聯集的元素個數滿足：
   $|E_1 \cup E_2| = |E_1| + |E_2| - |E_1 \cap E_2|$
3. 條件機率（Conditional Probability）：
   在已知事件 $B$ 發生的條件下，事件 $A$ 發生的條件機率定義為：
   $P(A \mid B) = \frac{P(A \cap B)}{P(B)} = \frac{|A \cap B|}{|B|}$
   其中樣本空間中每個解被選中的機率均相等（古典機率模型）。

---

解題方法

步驟一：定義事件與樣本空間
令 $S$ 為方程式 $x_1 + x_2 + x_3 + x_4 = 8$ 所有非負整數解組成的樣本空間。

• 定義事件 $A$ 為「$x_1 = 1$」。
• 定義事件 $B$ 為「$x_1 = 1$ 或 $x_2 = 1$」（即至少有一個等於 1）。

所求條件機率為 $P(A \mid B) = \frac{|A \cap B|}{|B|}$。

觀察事件交集 $A \cap B$：
由於事件 $A$ 為「$x_1 = 1$」，已經滿足「$x_1 = 1$ 或 $x_2 = 1$」，故 $A \subseteq B$，可得 $A \cap B = A$。
因此分子需要的元素個數即為 $|A|$。

步驟二：計算分子 $|A \cap B| = |A|$
當 $x_1 = 1$ 時，原方程式化簡為：
$1 + x_2 + x_3 + x_4 = 8 \implies x_2 + x_3 + x_4 = 7$
其中 $x_2, x_3, x_4 \ge 0$。
利用重複組合公式，非負整數解個數為：
$|A| = H^3_7 = \binom{3 + 7 - 1}{7} = \binom{9}{7} = \binom{9}{2} = \frac{9 \times 8}{2 \times 1} = 36$

核心觀念

本題考查離散數學中集合的遞迴定義（Recursive Definition of Sets）。
一個集合的遞迴定義包含三個關鍵部分：

1. 基礎步驟（Basis Step）：指定最基礎、初始存在於集合中的元素（通常為長度最短的基礎元素，如空字串 $\lambda$）。
2. 遞迴步驟（Recursive Step）：給定已知屬於該集合的元素，提供明確的規則來建構出新屬於該集合的元素。
3. 極小性條件（Extremal Clause）：集合僅包含由基礎步驟與有限次遞迴步驟所產生的元素（通常隱含於定義中）。

本題標的為「包含相同數量 0 與 1 的位元串集合 $S$」（Bit strings with the same number of zeros and ones）。

---

解題方法

設 $S$ 為由包含相同數量 0 與 1 的所有位元串所組成的集合。推導其遞迴定義如下：

1. 基礎步驟（Basis Step）

空字串 $\lambda$（或記作 $\epsilon$）包含 0 個 0 與 0 個 1，其 0 與 1 的數量相等（皆為 0）。因此基礎步驟定義為：
$\lambda \in S$

2. 遞迴步驟（Recursive Step）

若要從已知屬於 $S$ 的字串生成更長的合規位元串，需結合以下兩種結構：

• 包夾結構（Enclosure）：若 $w \in S$，在其兩端分別補上一個 0 與一個 1（即 $0w1$ 與 $1w0$），其 0 與 1 的數量皆各增加 1 個，兩者數量依然保持相等。
  $\text{若 } w \in S \implies 0w1 \in S \text{ 且 } 1w0 \in S$
• 串接結構（Concatenation）：若 $x \in S$ 且 $y \in S$，將 $x$ 與 $y$ 首尾相接形成 $xy$，其總 0 數為 $x$ 與 $y$ 的 0 數之和，總 1 數為 $x$ 與 $y$ 的 1 數之和，故 $xy$ 之 0 與 1 數量亦相等。
  $\text{若 } x, y \in S \implies xy \in S$

綜合上述，集合 $S$ 的完整遞迴定義為：

• Basis Step: $\lambda \in S$
• Recursive Step: 若 $x, y \in S$，則 $0x1 \in S$、$1x0 \in S$ 以及 $xy \in S$。

---

選項分析

本題為問答／定義題（非選擇題）。以下方針方針分析常見的定義嘗試與錯誤型態，說明為何部分直覺定義不具完備性：

• 分析一：僅定義 $0x1$ 與 $1x0$（缺乏串接規則 $xy$）—— 錯誤（缺乏完備性 Completeness）

核心觀念

本題考驗利用**普通生成函數（Ordinary Generating Function, OGF）**求解同物分給相異人的組合計數問題。

1. 生成函數建模：將每個相異受贈者可接收的物品數量限制轉化為多項式（或形式冪級數）的次方項，物品總數對應於冪級數中變數 $x$ 的指數。
2. 無窮等比級數閉合形式：
   $1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x} \quad (|x| < 1)$
3. 廣義二項式定理（Generalized Binomial Theorem）：
   $\frac{1}{(1-x)^n} = (1-x)^{-n} = \sum_{k=0}^{\infty} \binom{n+k-1}{k} x^k = \sum_{k=0}^{\infty} H_k^n x^k$
   其中 $[x^k](1-x)^{-n} = \binom{n+k-1}{k}$ 表示取 $x^k$ 項的係數。

---

解題方法

Step 1：建立單一兒童的生成函數因子
設第 $i$ 位兒童獲得 $e_i$ 個氣球（$i = 1, 2, 3, 4$）。
根據題目限制，每位兒童至少獲得 $2$ 個氣球，即 $e_i \ge 2$。
因此，代表單一兒童獲得氣球數量的生成函數因子 $f(x)$ 為：
$f(x) = x^2 + x^3 + x^4 + \cdots = x^2 (1 + x + x^2 + \cdots) = \frac{x^2}{1-x}$

Step 2：建構整體問題的生成函數
由於四位兒童為可區分（Distinguishable），將四位兒童的生成函數因子相乘，得到分配 10 個氣球給四位兒童的整體生成函數 $G(x)$：
$G(x) = [f(x)]^4 = \left( \frac{x^2}{1-x} \right)^4 = \frac{x^8}{(1-x)^4} = x^8 (1-x)^{-4}$

Step 3：萃取 $x^{10}$ 的係數並展開計算
分配 $10$ 個氣球的方法數，即為 $G(x)$ 中 $x^{10}$ 項的係數，記作 $[x^{10}] G(x)$：
$[x^{10}] G(x) = [x^{10}] \left( x^8 (1-x)^{-4} \right) = [x^2] (1-x)^{-4}$