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

核心觀念

本題旨在考驗離散領域中函數性質（Function Properties）的基本概念，特別是單射（One-to-One / Injective）與對射（Bijection / One-to-One Correspondence）的定義：

1. 單射（One-to-One / Injection）：設 $F: A \rightarrow B$ 為一函數。若對所有 $x_1, x_2 \in A$，當 $x_1 \neq x_2$ 時必有 $F(x_1) \neq F(x_2)$（同義逆否命題：若 $F(x_1) = F(x_2)$ 則必有 $x_1 = x_2$），則稱 $F$ 為單射。
2. 滿射（Onto / Surjection）：若對所有 $y \in B$，皆存在至少一個 $x \in A$ 使得 $F(x) = y$，則稱 $F$ 為滿射。
3. 對射（Bijection）：若函數 $F$ 同時滿足單射與滿射，則稱 $F$ 為對射（又稱一對一對應）。

---

解題方法

題目定義定義域 $S = \{0, 1\}^*$ 為由 0 與 1 所構成的所有有限長度字串集合，對應域為整數集 $\mathbb{Z}$。
函數 $F: S \rightarrow \mathbb{Z}$ 的規則為：對任意字串 $s \in S$，$F(s)$ 代表字串 $s$ 中數字 '1' 出現的總個數。

要判斷 $F$ 是否為單射（One-to-One），只需尋找反例（Counterexample）：
只要能找到兩個不同的字串 $s_1, s_2 \in S$ 滿足 $s_1 \neq s_2$，但經映射後 $F(s_1) = F(s_2)$，即可證明 $F$ 不為單射。

推導步驟：

1. 取字串 $s_1 = \text{"10"}$ 與 $s_2 = \text{"01"}$。顯然 $s_1 \neq s_2$。
2. 計算兩者經由 $F$ 對應的函數值：
   $F(s_1) = F(\text{"10"}) = 1$
   $F(s_2) = F(\text{"01"}) = 1$

核心觀念

本題旨在考驗**偏序集合（Partially Ordered Set，簡稱 Poset）**的定義與性質驗證。

1. 偏序集合（Poset）定義：
   設 $S$ 為一非空集合，$\leq$ 為定義在 $S$ 上的一個二元關係（Binary Relation）。若 $(S, \leq)$ 同時滿足以下三個條件，則稱其為偏序集合：
   • 自反性（Reflexivity）：對所有 $a \in S$，$a \leq a$。
   • 反對稱性（Antisymmetry）：對所有 $a, b \in S$，若 $a \leq b$ 且 $b \leq a$，則 $a = b$。
   • 遞移性（Transitivity）：對所有 $a, b, c \in S$，若 $a \leq b$ 且 $b \leq c$，則 $a \leq c$。
2. 逐分量比較關係（Componentwise Order / Product Order）：
   給定 $A = \{0, 1\}$，集合 $A^3 = A \times A \times A = \{(a_1, a_2, a_3) \mid a_1, a_2, a_3 \in \{0, 1\}\}$。題目定義的關係 $a \leq b \iff \forall i \in \{1, 2, 3\}, a_i \leq b_i$，即為利用實數標準小於等於關係所建立的逐分量偏序關係。

---

解題方法

欲判斷 $(A^3, \leq)$ 是否為偏序集合，必須針對 $A^3$ 中的元素逐一檢驗偏序的三大公理：

1. 驗證自反性（Reflexivity）：
   任取 $a = (a_1, a_2, a_3) \in A^3$。
   由於每個分量 $a_i \in \{0, 1\}$ 為實數，依實數標準小於等於關係的自反性可知：
   $a_1 \leq a_1, \quad a_2 \leq a_2, \quad a_3 \leq a_3$
   對所有 $1 \leq i \leq 3$ 皆有 $a_i \leq a_i$ 成立，根據題目定義即得 $a \leq a$。
   故關係 $\leq$ 滿足自反性。

2. 驗證反對稱性（Antisymmetry）：
   任取 $a = (a_1, a_2, a_3), b = (b_1, b_2, b_3) \in A^3$，並假設 $a \leq b$ 且 $b \leq a$。

   • 由 $a \leq b$ 可得：$a_1 \leq b_1, \, a_2 \leq b_2, \, a_3 \leq b_3$。
   • 由 $b \leq a$ 可得：$b_1 \leq a_1, \, b_2 \leq a_2, \, b_3 \leq a_3$。
     對每一個分量 $i \in \{1, 2, 3\}$，因 $a_i, b_i \in \{0, 1\}$ 滿足 $a_i \leq b_i$ 且 $b_i \leq a_i$，由實數的反對稱性可推得：
     $a_1 = b_1, \quad a_2 = b_2, \quad a_3 = b_3$
     因三個對應分量均相等，故元組 $a = b$。
     故關係 $\leq$ 滿足反對稱性。

核心觀念

• 偏序集（Poset）與偏序同構（Poset Isomorphism）：
  設 $(A, \preceq_A)$ 與 $(B, \preceq_B)$ 為兩個偏序集。若存在一個雙射函數 $f: A \to B$，滿足對任意 $x, y \in A$，均成立：
  $x \preceq_A y \iff f(x) \preceq_B f(y)$
  則稱偏序集 $(A, \preceq_A)$ 與 $(B, \preceq_B)$ 同構，記作 $(A, \preceq_A) \cong (B, \preceq_B)$。
• 直積偏序集（Product Poset）：
  對於偏序集 $P_1$ 與 $P_2$，其直積 $P_1 \times P_2$ 的偏序關係定義為分量逐項（bitwise / component-wise）比較。
• 正整數因數集與算術基本定理：
  若正整數 $N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$（其中 $p_i$ 為相異質因數），則 $N$ 的所有正因數集合在整除關係 $\mid$ 下，同構於直積偏序集 $\{0, 1, \dots, e_1\} \times \{0, 1, \dots, e_2\} \times \dots \times \{0, 1, \dots, e_k\}$。

---

解題方法

1. 分析偏序集 $(T, \preceq)$：
   三進位字元集為 $\{0, 1, 2\}$，其具備自然的大小順序 $0 < 1 < 2$。
   長度為 $2$ 的三進位字串集合 $T = \{a_1 a_2 \mid a_1, a_2 \in \{0, 1, 2\}\}$，偏序關係 $\preceq$ 為位元逐項比較（bitwise $\leq$），即：
   $a_1 a_2 \preceq b_1 b_2 \iff a_1 \leq b_1 \text{ 且 } a_2 \leq b_2$
   因此，偏序集 $(T, \preceq)$ 的結構即為直積偏序集 $\{0, 1, 2\} \times \{0, 1, 2\}$，共有 $3 \times 3 = 9$ 個元素。

2. 分析偏序集 $(F, \mid)$：
   將 $36$ 進行質因數分解：$36 = 2^2 \times 3^2$。
   $36$ 的所有正因數集合 $F$ 可表示為：
   $F = \{ 2^{x} \times 3^{y} \mid x, y \in \{0, 1, 2\} \}$
   共有 $(2+1) \times (2+1) = 9$ 個因數。
   根據整除的定義，對於 $m = 2^{x_1} 3^{y_1} \in F$ 與 $n = 2^{x_2} 3^{y_2} \in F$：

核心觀念

集合 $A$ 上的二元關係 (binary relation) $R$ 若要構成等價關係 (Equivalence Relation)，必須同時滿足以下三個條件：

1. 自反性 (Reflexivity)：對所有 $x \in A$，均有 $(x, x) \in R$。
2. 對稱性 (Symmetry)：對所有 $x, y \in A$，若 $(x, y) \in R$，則必有 $(y, x) \in R$。
3. 遞移性 (Transitivity)：對所有 $x, y, z \in A$，若 $(x, y) \in R$ 且 $(y, z) \in R$，則必有 $(x, z) \in R$。

---

解題方法

給定集合 $A = \{1, 2, 3, 4\}$ 與二元關係 $R = \{(1,1), (2,2), (3,3), (4,4), (2,3), (3,2), (2,4), (4,2)\}$。我們依序檢驗上述三個性質：

1. 檢驗自反性 (Reflexivity)：
   集合 $A$ 的元素為 $1, 2, 3, 4$。
   檢查對角線數對是否皆屬於 $R$：

   • $(1,1) \in R$
   • $(2,2) \in R$
   • $(3,3) \in R$
   • $(4,4) \in R$
     因為對所有 $x \in A$ 皆滿足 $(x,x) \in R$，故 $R$ 滿足自反性。

2. 檢驗對稱性 (Symmetry)：
   檢查 $R$ 中每一個數對 $(x,y)$ 顛倒後的數對 $(y,x)$ 是否也在 $R$ 中：

   • $(2,3) \in R \implies (3,2) \in R$
   • $(3,2) \in R \implies (2,3) \in R$
   • $(2,4) \in R \implies (4,2) \in R$
   • $(4,2) \in R \implies (2,4) \in R$
     其餘自反數對 $(x,x)$ 反轉後仍為自身。因此 $R$ 滿足對稱性。

3. 檢驗遞移性 (Transitivity)：
   尋找是否存在 $(x,y) \in R$ 與 $(y,z) \in R$，但 $(x,z) \notin R$ 的反例：

   • 觀察數對 $(3,2) \in R$ 與 $(2,4) \in R$（中間元素為 $2$）。若 $R$ 滿足遞移性，則必須包含 $(3,4)$。然而檢視關係 $R$，發現 $(3,4) \notin R$。

核心觀念

本題考查常係數二階線性齊次遞迴關係（Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients）的定義與判別。

一個 $n$ 階常係數線性遞迴關係的一般式為：
$C_0 a_k + C_1 a_{k-1} + C_2 a_{k-2} + \dots + C_n a_{k-n} = f(k)$

欲滿足「常係數二階線性齊次遞迴關係」，必須同時符合以下四項條件：

1. 二階（Second-order）：遞迴關係中出現的最大下標與最小下標相差恰為 $2$。即包含 $a_{k-2}$ 項（其係數 $C_2 \neq 0$），且不含任何 $a_{k-n}$（$n > 2$）的非零項。
2. 線性（Linear）：所有 $a_j$ 項均為一次方，且各 $a_j$ 項之間不得有相乘、平方、開方、超越函數等非線性組合。
3. 齊次（Homogeneous）：非齊次項（不含未知數序列 $a_j$ 的常數項或僅與 $k$ 有關的函數項）$f(k) = 0$。即移項後每一項均含有 $a_j$。
4. 常係數（Constant Coefficients）：乘以各 $a_j$ 項的係數 $C_i$ 皆為與 $k$ 無關的常數。

---

解題方法

將題目給定的 7 個範例逐一整理成標準型態，並依序檢驗「階數」、「線性」、「齊次」、「常係數」四個要件：

1. 範例 1： $a_k = 4a_{k-1} + 4a_{k-2} \implies a_k - 4a_{k-1} - 4a_{k-2} = 0$

   • 階數：最大下標為 $k$，最小下標為 $k-2$，階數 $k - (k-2) = 2$（二階）。
   • 線性：$a_k, a_{k-1}, a_{k-2}$ 皆為一次項（線性）。
   • 齊次：右式 $f(k) = 0$（齊次）。
   • 係數：係數分別為 $1, -4, -4$，皆為常數（常係數）。
   • 結果：符合。

2. 範例 2： $a_k = 2a_{k-1} + 7a_{k-3} \implies a_k - 2a_{k-1} - 7a_{k-3} = 0$

   • 階數：最小下標為 $k-3$，階數 $k - (k-3) = 3$（三階）。
   • 結果：不符合（階數錯誤，此為三階）。

3. 範例 3： $a_k = 3(a_{k-1})^2 + 2a_{k-2}$

   • 線性：包含 $(a_{k-1})^2$ 平方項（非線性）。
   • 結果：不符合（非線性）。

核心觀念

本題考查離散數學中的**圖形數（Figurate Numbers）與遞迴關係式（Recurrence Relation）**求和推導。

第 $n$ 個五角數 $P(n)$ 的圖形遞推特性為：每增加一層（即從第 $k-1$ 項擴展至第 $k$ 項），外圍會新增 3 條邊，每一條邊增加 $k$ 個點，但其中的 2 個頂點會被重複計算。因此，相較於前一項，點數增量為：
$P(k) - P(k-1) = 3k - 2 \quad (k \ge 2)$

初始條件為 $P(1) = 1$。五角數的一般式可表示為有限級數和：
$P(n) = P(1) + \sum_{k=2}^{n} (3k - 2) = 1 + \sum_{k=2}^{n} (3k - 2)$

---

解題方法

將有限級數和展開拆解計算：

1. 級數拆項：
   $P(n) = 1 + \sum_{k=2}^{n} (3k - 2) = 1 + 3\sum_{k=2}^{n} k - \sum_{k=2}^{n} 2$

2. 化簡級數項：

   • 其中的 $\sum_{k=2}^{n} k$ 即為 $2 + 3 + \dots + n$。
   • 其中的 $\sum_{k=2}^{n} 2$ 是將常數 2 從 $k=2$ 加到 $k=n$，總共有 $(n - 1)$ 項，故累加結果為 $2(n - 1)$。

3. 組合式子：
   將上述結果代回，得到：
   $P(n) = 1 + 3(2 + 3 + \dots + n) - 2(n - 1)$

4. 公式驗收化簡（求封閉形式 Closed Form）：
   $3(2 + 3 + \dots + n) = 3 \left[ \frac{n(n+1)}{2} - 1 \right] = \frac{3n^2 + 3n - 6}{2}$
   代入上式化簡：
   $P(n) = 1 + \frac{3n^2 + 3n - 6}{2} - 2n + 2 = \frac{3n^2 - n}{2}$
   此即著名的五角數封閉公式。比對選項表示法，選項 (a) 精確符合未化簡前的求和型式。

---

選項分析

• (a) $P(n) = 1 + 3(2+3+\dots+n) - 2(n-1)$：正確
  • 代數驗證：$1 + 3\left(\frac{n(n+1)}{2}-1\right) - 2(n-1) = \frac{3n^2 - n}{2}$，公式完全符合。
  • 數值驗證：
    • $n = 1 \implies P(1) = 1 + 3(0) - 2(0) = 1$
    • $n = 2 \implies P(2) = 1 + 3(2) - 2(1) = 5$
    • $n = 3 \implies P(3) = 1 + 3(2+3) - 2(2) = 12$
    • $n = 4 \implies P(4) = 1 + 3(2+3+4) - 2(3) = 22$

核心觀念

本題的核心為多重巢狀迴圈（Nested Loops）的執行次數計算，可轉化為離散數學中的級數求和與**組合計數（重複組合／帕斯卡曲棍球棒等式）**問題。

1. 巢狀迴圈求和表示：
   變數 increment 的最終值等於最內層程式碼執行的總次數，對應三重累加算式：
   $\text{increment} = \sum_{i=1}^{22} \sum_{j=1}^{i} \sum_{k=1}^{j} 1$

2. 關鍵公式：

   • 等差級數求和公式：
     $\sum_{k=1}^{n} k = \frac{n(n+1)}{2} = \binom{n+1}{2}$
   • 曲棍球棒等式（Hockey-stick Identity）：
     $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$
   • 重複組合（Combinations with Repetition）：
     從 $n$ 種相異物件中可重複選取 $r$ 個物件的組合數為：
     $H_r^n = \binom{n+r-1}{r}$

---

解題方法

提供兩種精確推導路徑：

方法一：級數逐層求和法（標準推導）

1. 第一層（最內層迴圈 $k$）：
   $\sum_{k=1}^{j} 1 = j$

2. 第二層（中間迴圈 $j$）：
   $\sum_{j=1}^{i} j = \frac{i(i+1)}{2} = \binom{i+1}{2}$

3. 第三層（最外層迴圈 $i$）：
   $\text{increment} = \sum_{i=1}^{22} \binom{i+1}{2} = \binom{2}{2} + \binom{3}{2} + \dots + \binom{23}{2}$
   套用曲棍球棒等式 $\sum_{m=2}^{23} \binom{m}{2} = \binom{24}{3}$：
   $\text{increment} = \binom{24}{3} = \frac{24 \times 23 \times 22}{3 \times 2 \times 1} = 4 \times 23 \times 22 = 2024$

方法二：重複組合轉化法（快速計數）

迴圈邊界約束條件為：
$1 \le k \le j \le i \le 22$
每一次 increment 加 1，均唯一對應一組滿足上述不等式的整數解 $(i, j, k)$。

這相當於從集合 $\{1, 2, \dots, 22\}$ 的 22 個整數中，可重複地取出 3 個數字（經排序後分別指定給 $k, j, i$）。因此總次數為重複組合數：

核心觀念

1. 演算法時間複雜度分析（Time Complexity Analysis）：透過計算演算法中「基本運算（Basic Operation）」在最壞情況下的執行總次數 $T(n)$，來推導其漸近時間複雜度。
2. 迴圈迭代與級數求和（Summation of Nested Loops）：對於嵌套迴圈（Nested Loops），外層與內層迴圈的執行次數可表示為求和公式：
   $T(n) = \sum_{k=\text{start}}^{\text{end}} (\text{內層迴圈執行次數})$
3. 等差級數求和公式：
   $\sum_{j=1}^{m} j = 1 + 2 + \dots + m = \frac{m(m+1)}{2}$
4. 大 $O$ 記號（Big-$O$ Notation）：描述函數成長率的上界（Upper Bound），僅保留最高次方項並忽略常數係數。

---

解題方法

1. 確定基本運算

在本段程式碼中，最核心且執行次數最多的基本運算為內層迴圈的條件比較：if max<a[i]。

2. 計算各層迴圈執行次數

• 外層迴圈（Outer loop）：控制變數 $k$ 從 $1$ 增加至 $n-1$。
• 內層迴圈（Inner loop）：對於每一個固定的 $k$，控制變數 $i$ 從 $k+1$ 執行至 $n$。
  內層迴圈對應的比較次數為：
  $(n) - (k+1) + 1 = n - k \text{ 次}$

3. 推導總比較次數 $T(n)$

將所有 $k$ 值對應的內層比較次數累加：
$T(n) = \sum_{k=1}^{n-1} (n - k)$

展開該求和式：

• 當 $k = 1$ 時，內層執行 $n - 1$ 次。
• 當 $k = 2$ 時，內層執行 $n - 2$ 次。
• $\dots$
• 當 $k = n - 1$ 時，內層執行 $1$ 次。

因此，$T(n)$ 為從 $1$ 到 $n-1$ 的等差級數和：

核心觀念

本題考查演算法的平均複雜度／期望值（Average-case Complexity / Expected Value）分析與迴圈執行次數計算。

1. 期望值公式：
   設離散隨機變數 $X$ 表示演算法執行 N mod i 的次數。當輸入 $N \in \{2, 3, 4, 5, 6, 7, 8\}$ 之出現機率均等（即均勻分布 $P(N) = \frac{1}{7}$）時，平均執行次數（期望值）定義為：
   $E[X] = \sum_{N=2}^{8} X(N) \cdot P(N) = \frac{1}{7} \sum_{N=2}^{8} X(N)$

2. 迴圈終止條件與質因數關係：
   此演算法自 $i = 2$ 開始每次將 $i$ 加 $1$，直到 $N \bmod i = 0$ 為止。這表示迴圈會在找到 $N$ 的最小質因數 $p(N)$ 時終止。因此，對於給定的 $N$，檢驗條件 (N mod i) ≠ 0 的總次數等於 $p(N) - 1$ 次。

---

解題方法

計算平均次數的關鍵在於逐一分析每一個可能的 $N$ 值對應的 N mod i 執行次數：

1. 當 $N = 2$ 時：

   • 初始 $i = 2$，檢查條件 (2 mod 2) ≠ 0 $\implies$ 0 ≠ 0（結果為假），結束迴圈。
   • N mod i 執行次數：$1$ 次。

2. 當 $N = 3$ 時：

   • $i = 2$：檢查 (3 mod 2) ≠ 0 $\implies$ 1 ≠ 0（真），執行 $i \leftarrow 3$。
   • $i = 3$：檢查 (3 mod 3) ≠ 0 $\implies$ 0 ≠ 0（假），結束迴圈。
   • N mod i 執行次數：$2$ 次。

3. 當 $N = 4$ 時：

   • 初始 $i = 2$，檢查條件 (4 mod 2) ≠ 0 $\implies$ 0 ≠ 0（假），結束迴圈。
   • N mod i 執行次數：$1$ 次。

4. 當 $N = 5$ 時：

   • $i = 2$：(5 mod 2) ≠ 0（真），$i \leftarrow 3$。
   • $i = 3$：(5 mod 3) ≠ 0（真），$i \leftarrow 4$。
   • $i = 4$：(5 mod 4) ≠ 0（真），$i \leftarrow 5$。
   • $i = 5$：(5 mod 5) ≠ 0（假），結束迴圈。
   • N mod i 執行次數：$4$ 次。

5. 當 $N = 6$ 時：

   • 初始 $i = 2$，檢查條件 (6 mod 2) ≠ 0 $\implies$ 0 ≠ 0（假），結束迴圈。
   • N mod i 執行次數：$1$ 次。

6. 當 $N = 7$ 時：

   • $i$ 從 $2$ 遞增測試至 $6$，條件皆為真；至 $i = 7$ 時 (7 mod 7) ≠ 0（假），結束迴圈。
   • N mod i 執行次數：$6$ 次。

核心觀念

本題考查**遞迴（Recursion）**的基本定義、執行機制與記憶體管理特性，涵蓋以下核心要點：

1. 資料 structures 與 Call Stack：系統利用 Stack（堆疊）維護函式呼叫過程，其操作遵循**後進先出（LIFO, Last In First Out）**原則。
2. 記憶體配置（Stack Frame / Activation Record）：每次函式呼叫皆會在 Call Stack 上建立一個堆疊框架（Stack Frame），用以儲存返回地址、傳入參數與區域變數，會消耗記憶體資源。
3. 遞迴的結構要件：遞迴函式必須包含終止條件（Terminating Condition / Base Case）與遞迴步驟（Recursive Step），否則會導致無窮遞迴（Infinite Recursion）並引發 Stack Overflow。
4. 遞迴的特性與權衡（Elegance vs. Efficiency）：遞迴能將複雜問題簡化為結構相同的子問題，程式碼具備高度簡潔優雅性（Elegance）；但由於頻繁的函式呼叫負擔（Function Call Overhead），其**執行與空間效率（Efficiency）**通常低於迭代（Iteration）。

---

解題方法

本題為觀念計數題，題目要求選出**錯誤（incorrect）**敘述的總數量。
切入點為針對 5 個敘述逐一審視其語意邏輯、電腦科學名詞定義及記憶體運作機制，確定每個敘述的真偽（True / False）後進行統計。

---

選項分析

• 敘述一：「C language maintains the recursive steps via stack data structure, which follows the "first in first out" principle.」

  • 判定：錯誤（Incorrect）
  • 解析：C 語言在處理遞迴（及一般函式呼叫）時，雖然確實是利用 Stack（堆疊） 來記錄呼叫狀態，但 Stack 所遵循的存取原則為**「後進先出」（LIFO, Last In First Out）**，而非「先進先出」（FIFO, First In First Out）。FIFO 為 Queue（佇列）的特性。

• 敘述二：「When we use recursion to solve problems, we are interested in elegance and efficiency.」

  • 判定：錯誤（Incorrect）
  • 解析：使用遞迴解決問題的核心目的在於追求程式碼的簡潔優雅（Elegance）與可讀性，而非「效率（Efficiency）」。