114 年 國立中山大學資訊工程學系碩士班甲組《離散數學》

核心觀念

1. 迴圈執行次數與組合計數（Combinatorics）：多重巢狀迴圈的總執行次數問題，本質為計算滿足 $1 \le k \le j \le i \le n$ 的三元組 $(i, j, k)$ 個數。此累加和可透過曲棍球棒恆等式（Hockey-stick Identity）或重複組合公式求得。
2. 變數累加的數理模型：變數 increment 在每次最內層迴圈執行時均加 $1$，因此第 $m$ 次執行時 increment 的值為 $m$；sum 則是將每次更新後的 increment 連續加總，故最終結果等於前 $N$ 個正整數的級數和 $\sum_{m=1}^{N} m = \frac{N(N+1)}{2}$，其中 $N$ 為最內層迴圈的總執行次數。

---

解題方法

本題解法分為兩個關鍵推導步驟：

步驟一：計算最內層迴圈的總執行次數 $N$

迴圈範圍分別為 $i$ 從 $1$ 到 $12$、$j$ 從 $1$ 到 $i$、$k$ 從 $1$ 到 $j$。總執行次數 $N$ 可表示為三重求和式：
$N = \sum_{i=1}^{12} \sum_{j=1}^{i} \sum_{k=1}^{j} 1$

先計算最內層與中間層的求和：
$\sum_{k=1}^{j} 1 = j$
$\sum_{j=1}^{i} j = \frac{i(i+1)}{2} = \binom{i+1}{2}$

將結果代回最外層對 $i$ 的求和式：
$N = \sum_{i=1}^{12} \binom{i+1}{2} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \dots + \binom{13}{2}$

利用曲棍球棒恆等式 $\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$（其中 $r=2, n=13$）：
$N = \binom{13+1}{2+1} = \binom{14}{3} = \frac{14 \times 13 \times 12}{3 \times 2 \times 1} = 364$

即最內層迴圈區塊共執行 $364$ 次。

步驟二：推導變數 sum 的最終數值

設最內層迴圈（begin ... end）第 $m$ 次執行（$m = 1, 2, \dots, N$）：

• 執行 increment = increment + 1 後，increment 的值變為 $m$。

核心觀念

本題考查**良序原理（Well-Ordering Principle, WOP）與第一數學歸納法原理（Principle of Mathematical Induction, PMI）**之間的導出關係。

相關定義與定理如下：

1. 良序原理（Well-Ordering Principle, WOP）：
   正整數集合 $\mathbb{Z}^+$（或非負整數集合 $\mathbb{N}$）的任意非空子集 $S$，必然存在一個最小元素（least element）。即：
   $\forall S \subseteq \mathbb{Z}^+, S \neq \emptyset \implies \exists m \in S, \forall x \in S (m \le x)$

2. 第一數學歸納法原理（Principle of Mathematical Induction, PMI）：
   設 $P(n)$ 為定義於正整數 $n \in \mathbb{Z}^+$ 上的命題。若滿足下列條件：

   • 基礎步驟（Base Step）：$P(1)$ 為真。
   • 歸納步驟（Inductive Step）：對任意 $k \in \mathbb{Z}^+$，若 $P(k)$ 為真，則 $P(k+1)$ 亦為真。

   則對所有正整數 $n \in \mathbb{Z}^+$，$P(n)$ 皆為真。

---

解題方法

本題採用**反證法（Proof by Contradiction）結合良序原理（WOP）**進行推導。

完整證明推導步驟：

1. 建立反例集合（Set of Counterexamples）：
   假設 PMI 的前提成立，即：
   (i) $P(1)$ 為真。
   (ii) 對所有 $k \in \mathbb{Z}^+$，若 $P(k)$ 為真，則 $P(k+1)$ 為真。

   定義使命題 $P(n)$ 為假的所有正整數所構成的集合 $S$：
   $S = \{ n \in \mathbb{Z}^+ \mid P(n) \text{ 為假} \}$
   欲證明 $P(n)$ 對所有正整數 $n$ 皆成立，等價於證明 $S = \emptyset$。

2. 引導反證假設與套用良序原理：
   假設 $S \neq \emptyset$（即存在使 $P(n)$ 為假的反例）。

核心觀念

1. 滿射函數（Surjective Function / Onto Function）計數
   設定義域 $A$ 的元素個數為 $|A| = n$，值域 $C$ 的元素個數為 $|C| = k$。從 $A$ 映至 $C$ 的滿射函數個數（即值域中每個元素都至少被對應一次）可透過排容原理（Inclusion-Exclusion Principle）計算：
   $N(n, k) = k! \cdot S(n, k) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k - j)^n$
   其中 $S(n, k)$ 為第二類史特林數（Stirling Numbers of the Second Kind），代表將 $n$ 個相異元素分割成 $k$ 個非空非標號子集的組合數。

2. 組合計數與乘法原理
   若值域未指定具體元素、僅指定元素個數為 $k$，則需先從到達域（Codomain）$B$（設 $|B| = m$）中任選 $k$ 個元素作為值域，選法有 $\binom{m}{k}$ 種；選定後再乘以將 $A$ 滿射至該 $k$ 個元素的函數總數。

---

解題方法

由題意知：

• 定義域 $A = \{1,2,3,4,5,6,7,8,9\}$，故 $|A| = n = 9$。
• 到達域 $B = \{a,b,c,d,e,f,g,h\}$，故 $|B| = m = 8$。

1. (a) 子題切入點：
   條件 $f(A) = \{a,b,c\}$ 表示值域精確等於三個指定的元素集合 $\{a,b,c\}$。這意味著 $f$ 是從大小為 $9$ 的集合 $A$ 映射至大小為 $3$ 的固定集合 $\{a,b,c\}$ 的滿射函數。直接代入滿射函數排容公式即可求得。

2. (b) 子題切入點：
   條件 $|f(A)| = 3$ 表示值域大小為 3，但元素可以是到達域 $B$ 中的任意 3 個元素。解題分為兩步驟：

   • 步驟一：從 $|B| = 8$ 的到達域中選擇 3 個元素作為值域，組合數為 $\binom{8}{3}$。
   • 步驟二：對於每一組選定的 3 元素集合，計算從 $A$ 到該集合的滿射函數個數（即 (a) 小題之結果）。
   • 由乘法原理，將步驟一與步驟二結果相乘即得解答。

---

選項與子題分析

(a) 計算 $f(A) = \{a,b,c\}$ 的函數個數

對每個元素 $a_i$，令 $I_i$、$D_i$ 分別為以 $a_i$ 結尾的最長遞增、遞減子序列長度。

若不存在長度 $3$ 的遞增或遞減子序列，則

$$(I_i,D_i)\in\{1,2\}\times\{1,2\},$$

核心觀念

本題要求建立一個輸入、輸出皆為 $\{0,1\}$ 的有限狀態機，辨識語言

$$L=\{0,1\}^*\{10\}\cup\{0,1\}^*\{00\}.$$

其中 $\{0,1\}^*$ 表示所有由 $0$、$1$ 組成的有限字串，因此 $L$ 包含：

• 以 $10$ 結尾的字串；
• 以 $00$ 結尾的字串。

換句話說，機器只需判斷「目前讀入的字串最後兩個符號是否為 $10$ 或 $00$」。

本題可採用 Mealy machine 表示法，令每條邊標示為：

$$\text{輸入}/\text{輸出}.$$

輸出 $1$ 表示目前讀入的完整字串屬於 $L$，輸出 $0$ 表示不屬於 $L$。

---

解題方法

建立三個狀態：

• $q_s$：尚未讀入任何符號；
• $q_0$：目前字串最後一個符號是 $0$；
• $q_1$：目前字串最後一個符號是 $1$。

讀入新符號時，只需根據前一個符號與目前輸入，判斷最後兩個符號是否為 $00$ 或 $10$。

狀態轉移如下：

目前狀態	輸入	下一狀態	輸出	判斷
$q_s$	$0$	$q_0$	$0$	字串僅為 $0$，尚未形成長度 2 的後綴
$q_s$	$1$	$q_1$	$0$	字串僅為 $1$，尚未形成長度 2 的後綴
$q_0$	$0$	$q_0$	$1$	最後兩碼為 $00$
$q_0$	$1$	$q_1$	$0$	最後兩碼為 $01$
$q_1$	$0$	$q_0$	$1$	最後兩碼為 $10$
$q_1$	$1$	$q_1$	$0$	最後兩碼為 $11$

因此狀態圖可用下列方式表示：

• 初始狀態為 $q_s$；
• $q_s \xrightarrow{0/0} q_0$；
• $q_s \xrightarrow{1/0} q_1$；
• $q_0 \xrightarrow{0/1} q_0$；
• $q_0 \xrightarrow{1/0} q_1$；
• $q_1 \xrightarrow{0/1} q_0$；
• $q_1 \xrightarrow{1/0} q_1$。

其中：

$$\delta(q_s,0)=q_0,\qquad \lambda(q_s,0)=0$$ $$\delta(q_s,1)=q_1,\qquad \lambda(q_s,1)=0$$ $$\delta(q_0,0)=q_0,\qquad \lambda(q_0,0)=1$$

核心觀念

本題考查離散數學中遞迴關係式（Recurrence Relation）的建立與求解，涉及以下核心觀念與工具：

1. 加法原理與乘法原理：透過分析序列最後一個執行的程式長度與種類，進行狀態轉移。
2. 齊次線性遞迴關係式（Homogeneous Linear Recurrence Relation）：確定階數與初始條件（Initial Conditions）。
3. 特徵方程式法（Characteristic Equation Method）：寫出對應的多項式特徵根形式。
4. 生成函數法（Generating Function Method）：將遞迴關係轉換為冪級數代數式求解。
5. 組合計數（Combinatorial Counting）：利用二項式係數（Binomial Coefficients）推導出不需解特徵根的顯式加總解（Explicit Summation Form）。

---

解題方法

(a) 小題 (a) 詳解

1. 建立遞迴關係式與初始條件

設 $a_n$ 為執行總時間為 $n$ 秒的相異程式執行序列數。

考慮長度為 $n$ 秒的序列最後一個執行的程式：

• 情況一：最後一個程式為 $P_1$（耗時 1 秒）。前 $n-1$ 秒的執行序列方法數為 $a_{n-1}$。
• 情況二：最後一個程式為 $P_2$（耗時 4 秒）。前 $n-4$ 秒的執行序列方法數為 $a_{n-4}$。

依據加法原理，對於 $n \ge 4$，遞迴關係式為：
$a_n = a_{n-1} + a_{n-4}$

初始條件（$n = 0, 1, 2, 3$）：

• $a_0 = 1$（0 秒，空序列 1 種）
• $a_1 = 1$（僅有 $P_1$）
• $a_2 = 1$（僅有 $P_1 P_1$）
• $a_3 = 1$（僅有 $P_1 P_1 P_1$）

---

2. 求解遞迴關係式

【解法一：生成函數法】
設生成函數 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。將遞迴關係式兩邊同乘以 $x^n$ 並對 $n \ge 4$ 加總：
$\sum_{n=4}^{\infty} a_n x^n = \sum_{n=4}^{\infty} a_{n-1} x^n + \sum_{n=4}^{\infty} a_{n-4} x^n$
$A(x) - a_0 - a_1 x - a_2 x^2 - a_3 x^3 = x (A(x) - a_0 - a_1 x - a_2 x^2) + x^4 A(x)$

帶入初始條件 $a_0=1, a_1=1, a_2=1, a_3=1$：
$A(x) - (1 + x + x^2 + x^3) = x (A(x) - 1 - x - x^2) + x^4 A(x)$
$A(x) - 1 - x - x^2 - x^3 = x A(x) - x - x^2 - x^3 + x^4 A(x)$
$A(x)(1 - x - x^4) = 1$
$A(x) = \frac{1}{1 - x - x^4}$

【解法二：特徵方程式法】
對應的 4 階齊次線性遞迴特徵方程式為：
$r^4 - r^3 - 1 = 0$
若設其四根為 $r_1, r_2, r_3, r_4$，則通解可表示為：
$a_n = C_1 r_1^n + C_2 r_2^n + C_3 r_3^n + C_4 r_4^n$
其中常數 $C_1, C_2, C_3, C_4$ 由初始條件 $a_0=1, a_1=1, a_2=1, a_3=1$ 決定。

【解法三：組合顯式解】
若在 $n$ 秒的序列中使用了 $k$ 個 $P_2$ 程式（$0 \le k \le \lfloor n/4 \rfloor$）：

• $k$ 個 $P_2$ 佔用 $4k$ 秒，剩餘 $n-4k$ 秒由 $n-4k$ 個 $P_1$ 填滿。
• 總程式個數為 $k + (n-4k) = n-3k$ 個。
• 從 $n-3k$ 個位置中選出 $k$ 個安排 $P_2$ 的方法數為 $\binom{n-3k}{k}$。

因此，$a_n$ 的顯式組合解為：
$a_n = \sum_{k=0}^{\lfloor n/4 \rfloor} \binom{n - 3k}{k}$

---

(b) 小題 (b) 詳解

1. 建立遞迴關係式與初始條件

設 $b_n$ 為執行總時間為 $n$ 秒的相異程式執行序列數。

此題中 $P_2$ 包含 4 種相異的任務（設為 $P_{2,1}, P_{2,2}, P_{2,3}, P_{2,4}$），每一種皆耗時 4 秒，且視為不同程式。

考慮長度為 $n$ 秒的序列最後一個執行的程式：

• 情況一：最後一個程式為 $P_1$（1 種選擇）。前 $n-1$ 秒的執行方法數為 $b_{n-1}$。
• 情況二：最後一個程式為 $P_2$ 的某種任務（4 種選擇）。前 $n-4$ 秒的執行方法數為 $4 b_{n-4}$。

設豬肉、雞肉、牛肉盒數分別為 $p,c,b$，則

$p+c+b=n,\qquad p,c,b\ge 0,$

且 $b$ 必須為偶數。令 $b=2k$，其中 $0\le k\le\lfloor n/2\rfloor$。固定 $k$ 後，

$p+c=n-2k$

共有 $n-2k+1$ 組非負整數解。因此總數為

核心觀念

本題考查組合數學中的排列計數與古典機率，核心解題工具有兩種主流觀念：

1. 指數生成函數（Exponential Generating Function, EGF）：
   在處理有順序的排列問題且各元素出現次數具備奇偶性限制時，指數生成函數是最標準且通用的解法：
   • 出現任意次數的生成項：$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$
   • 出現偶數次（含 0 次）的生成項：$\cosh(x) = \frac{e^x + e^{-x}}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots$
   • 出現奇數次的生成項：$\sinh(x) = \frac{e^x - e^{-x}}{2} = x + \frac{x^3}{3!} + \frac{x^5}{5!} + \cdots$
2. 隨機變數期望值與奇偶投影法（Parity Indicator Method）：
   利用 $(-1)^k$ 的正負號判定奇偶性，並透過獨立隨機變數之期望值性質進行快速求值。

---

解題方法

方法一：指數生成函數法（標準正規解法）

八進位（Octal）系統共包含 8 個數字：$\{0, 1, 2, 3, 4, 5, 6, 7\}$。

1. 建立各數字的生成項：

   • 數字「3」出現偶數次，生成項為 $\frac{e^x + e^{-x}}{2}$
   • 數字「7」出現偶數次，生成項為 $\frac{e^x + e^{-x}}{2}$
   • 其餘 6 個數字 $\{0, 1, 2, 4, 5, 6\}$ 出現次數無限制，各自的生成項均為 $e^x$

2. 建立整體指數生成函數 $G(x)$：

   $$\begin{aligned} G(x) &= \left(\frac{e^x + e^{-x}}{2}\right) \cdot \left(\frac{e^x + e^{-x}}{2}\right) \cdot (e^x)^6 \\ &= \left(\frac{e^{2x} + 2 + e^{-2x}}{4}\right) \cdot e^{6x} \\ &= \frac{e^{8x} + 2e^{6x} + e^{4x}}{4} \end{aligned}$$

3. 求長度為 $n = 28$ 之合法序列總數 $a_{28}$：
   將各項展開為 Maclaurin 級數：

   $$G(x) = \frac{1}{4} \sum_{n=0}^{\infty} \left( 8^n + 2 \cdot 6^n + 4^n \right) \frac{x^n}{n!}$$

   因此長度為 $n$ 的合法排列數為 $\frac{x^n}{n!}$ 的係數 $a_n$：

   $$a_n = \frac{8^n + 2 \cdot 6^n + 4^n}{4}$$

   代入 $n = 28$：

   $$a_{28} = \frac{8^{28} + 2 \cdot 6^{28} + 4^{28}}{4}$$

4. 計算機率：
   長度為 28 的八進位序列總數為 $|\Omega| = 8^{28}$。故所求機率 $P$ 為：

   $$\begin{aligned} P &= \frac{a_{28}}{8^{28}} \\ &= \frac{8^{28} + 2 \cdot 6^{28} + 4^{28}}{4 \cdot 8^{28}} \\ &= \frac{1}{4} \left[ 1 + 2\left(\frac{6}{8}\right)^{28} + \left(\frac{4}{8}\right)^{28} \right] \\ &= \frac{1}{4} + \frac{1}{2}\left(\frac{3}{4}\right)^{28} + \frac{1}{4}\left(\frac{1}{2}\right)^{28} \end{aligned}$$

---

方法二：期望值奇偶濾波法（快速驗算法）

核心觀念

本題考查二階非齊次常係數線性遞迴關係（Second-order Non-homogeneous Linear Recurrence Relation with Constant Coefficients）的求解。

求解此類遞迴關係式的核心原理為解的疊加原理（Superposition Principle）：
全解（General Solution）$a_n$ 可拆解為齊次解（Homogeneous Solution）$a_n^{(h)}$ 與特解（Particular Solution）$a_n^{(p)}$ 之和：
$a_n = a_n^{(h)} + a_n^{(p)}$

1. 齊次解 $a_n^{(h)}$：將非齊次項令為 $0$，利用特徵方程式（Characteristic Equation）求出特徵根後構建。
2. 特解 $a_n^{(p)}$：根據非齊次項 $g(n) = 9n$ 的形式，使用未定係數法（Method of Undetermined Coefficients）假設特解形式並帶入求出係數。
3. 未定常數求解：將初始條件 $a_0 = 1, a_1 = 1$ 代入全解 $a_n$，解出齊次解中的線性組合係數。

---

解題方法

第一步：求解齊次解 $a_n^{(h)}$

考慮對應的齊次遞迴關係式：
$a_{n+2} - 7a_{n+1} + 12a_n = 0$

寫出其特徵方程式：
$r^2 - 7r + 12 = 0$

因式分解得：
$(r - 3)(r - 4) = 0 \implies r_1 = 3, \; r_2 = 4$

由於特徵根為兩個相異實根，故齊次解為：
$a_n^{(h)} = c_1 \cdot 3^n + c_2 \cdot 4^n \quad (c_1, c_2 \text{ 為常數})$

---

第二步：求解特解 $a_n^{(p)}$

原式的非齊次項為 $g(n) = 9n$，屬於一次多項式（即 $g(n) = (9n) \cdot 1^n$）。
由於 $s = 1$ 並非齊次遞迴式的特徵根，故可設特解形式為一次多項式：
$a_n^{(p)} = An + B$

將 $a_n^{(p)}$ 代回原非齊次遞迴關係式 $a_{n+2} - 7a_{n+1} + 12a_n = 9n$：
$[A(n+2) + B] - 7[A(n+1) + B] + 12[An + B] = 9n$

展開並依 $n$ 的同次項進行合併整理：
$An + 2A + B - 7An - 7A - 7B + 12An + 12B = 9n$
$(A - 7A + 12A)n + (2A - 7A + B - 7B + 12B) = 9n$
$6An + (-5A + 6B) = 9n$

對比等號兩邊 $n$ 的同次項係數：

$$\begin{cases} 6A = 9 \\ -5A + 6B = 0 \end{cases}$$

解出係數：
$A = \frac{3}{2}, \quad B = \frac{5}{4}$

因此，特解為：
$a_n^{(p)} = \frac{3}{2}n + \frac{5}{4}$

---

第三步：合併為全解並帶入初始條件

將齊次解與特解相加得到全解：
$a_n = c_1 \cdot 3^n + c_2 \cdot 4^n + \frac{3}{2}n + \frac{5}{4}$

帶入初始條件 $a_0 = 1$ 與 $a_1 = 1$：

1. 當 $n = 0$ 時：
   $a_0 = c_1 \cdot 3^0 + c_2 \cdot 4^0 + \frac{3}{2}(0) + \frac{5}{4} = 1$