109 年 國立中山大學資訊工程學系碩士班甲組《離散數學與演算法》

核心觀念

1. 非負整數解個數與重複組合（Combinations with Repetition）
   對於線性方程 $y_1 + y_2 + \cdots + y_k = n$，若要求其「非負整數解」（$y_i \ge 0$）的組數，可使用重複組合公式：
   $H^k_n = \binom{n+k-1}{n} = \binom{n+k-1}{k-1}$

2. 變數平移與平移轉換（Variable Transformation）
   當變數設有下限條件 $x_i \ge c_i$ 時，可定義新變數 $y_i = x_i - c_i \ge 0$，將原式改寫為以非負整數為主的標準形式。

3. 排容原理與補集扣除法（Inclusion-Exclusion Principle / Complementary Counting）
   當變數設有上限條件（例如 $x_i \le d_i$）時，可利用補集概念：
   $\text{符合條件的解數} = \text{無上限約束的總解數} - \text{違反上限條件（即 } x_i \ge d_i + 1 \text{）的解數}$

---

解題方法

(a) 求 $x_1 + x_2 + x_3 + x_4 = 64$ 且 $x_i \ge 1$ ($1 \le i \le 4$) 的整數解個數

1. 變數轉換：
   因為 $x_i \ge 1$，令 $y_i = x_i - 1 \ge 0$ （對應 $i = 1, 2, 3, 4$）。
   代入原方程式：
   $(y_1 + 1) + (y_2 + 1) + (y_3 + 1) + (y_4 + 1) = 64$
   $y_1 + y_2 + y_3 + y_4 = 60$

2. 套用重複組合公式：
   此問題轉化為求解 $y_1 + y_2 + y_3 + y_4 = 60$ 的非負整數解個數：
   $H^4_{60} = \binom{60 + 4 - 1}{60} = \binom{63}{60} = \binom{63}{3}$

3. 數值計算：
   $\binom{63}{3} = \frac{63 \times 62 \times 61}{3 \times 2 \times 1} = 21 \times 31 \times 61 = 39711$

---

(b) 求 $x_1 + x_2 + x_3 + x_4 = 64$ 且 $x_1, x_2, x_3 > 2$、$0 < x_4 \le 14$ 的整數解個數

1. 條件離散化與變數平移：
   在整數域中，條件轉換如下：

   • $x_1, x_2, x_3 > 2 \implies x_1, x_2, x_3 \ge 3$
   • $0 < x_4 \le 14 \implies 1 \le x_4 \le 14$

   定義非負整數變數：

   • $y_1 = x_1 - 3 \ge 0 \implies x_1 = y_1 + 3$
   • $y_2 = x_2 - 3 \ge 0 \implies x_2 = y_2 + 3$
   • $y_3 = x_3 - 3 \ge 0 \implies x_3 = y_3 + 3$
   • $y_4 = x_4 - 1 \ge 0 \implies x_4 = y_4 + 1$

   由於 $x_4 \le 14$，故 $y_4 + 1 \le 14 \implies y_4 \le 13$。

2. 化簡方程式：
   $(y_1 + 3) + (y_2 + 3) + (y_3 + 3) + (y_4 + 1) = 64$
   $y_1 + y_2 + y_3 + y_4 = 54, \quad \text{其中 } y_1, y_2, y_3, y_4 \ge 0 \text{ 且 } y_4 \le 13$

核心觀念

本題旨在考驗離散數學中「數論（Number Theory）」的基本定義與雙向邏輯證明技巧。主要使用的定義如下：

1. 質數（Prime Number）之定義：整數 $p > 1$ 若除了 $1$ 與 $p$ 本身之外沒有其他正因數，則稱 $p$ 為質數。
2. 整除（Divisibility）之定義：設 $a, b \in \mathbb{Z}$ 且 $a \neq 0$。若存在一整數 $k$ 使得 $b = k \cdot a$，則稱 $a$ 整除 $b$，記作 $a \mid b$。此時 $a$ 為 $b$ 的因數。
3. 充要條件（If and Only If, $\iff$）證明架構：欲證明命題 $A \iff B$，必須分別證明「必要性（$A \implies B$）」與「充分性（$B \implies A$）」兩個方向。

---

解題方法

已知 $p, q$ 皆為質數，欲證明 $p \mid q \iff p = q$。推導步驟如下：

1. 必要性證明（$\implies$）：已知 $p \mid q$，證明 $p = q$

• 由整除之定義，若 $p \mid q$，表示 $p$ 是 $q$ 的一個正因數。
• 由質數之定義，已知 $q$ 為質數，故 $q$ 的所有正因數集合唯有 $\{1, q\}$。
• 因此，$p$ 必屬於該集合，即 $p = 1$ 或 $p = q$。
• 再由質數之定義，已知 $p$ 本身亦為質數，故 $p > 1$（即 $p \neq 1$）。

因為

$$99373n+342246\equiv342246\pmod n,$$

故

$$n\mid(99373n+342246)\iff n\mid342246.$$

由

$$(g\circ f)(x)=1-(ax+b)+(ax+b)^2$$

展開得

$$a^2x^2+a(2b-1)x+(b^2-b+1)=9x^2-9x+3.$$

比較係數：

核心觀念

1. 指數生成函數（Exponential Generating Function, EGF）之定義：
   對於一個無窮數列 $\langle a_n \rangle_{n=0}^{\infty} = \langle a_0, a_1, a_2, a_3, \dots \rangle$，其指數生成函數 $A(x)$ 定義為：
   $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = a_0 + a_1 x + a_2 \frac{x^2}{2!} + a_3 \frac{x^3}{3!} + \dots$

2. 無窮等比級數求和公式（Geometric Series Formula）：
   當 $|x| < 1$ 時，公比為 $x$ 的無窮等比級數可收斂並表示為閉合型態（Closed Form）：
   $\sum_{n=0}^{\infty} x^n = 1 + x + x^2 + x^3 + \dots = \frac{1}{1-x}$

---

解題方法

步驟一：確定數列之通項
題目給定數列為 $0!, 1!, 2!, 3!, \dots$，其通項（一般項）可表示為：
$a_n = n!, \quad \forall n \ge 0$

步驟二：代入指數生成函數定義
將通項 $a_n = n!$ 代入指數生成函數 $A(x)$ 之定義式中：
$A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} = \sum_{n=0}^{\infty} n! \cdot \frac{x^n}{n!}$

步驟三：項次相消與化簡
由於分子的 $n!$ 與分母的 $n!$ 互相抵消：

核心觀念

本題考查**二階常係數齊次線性遞迴關係式（Second-Order Homogeneous Linear Recurrence Relation with Constant Coefficients）**的求解。核心觀念包含以下兩大階段：

1. 待定係數求法：利用已知的數列前幾項（初始條件與後續項），代入遞迴關係式建立聯立方程式，解出未知的常數係數 $b$ 與 $c$。
2. 齊次遞迴關係式通解：
   • 對於形式為 $a_{n+2} + b a_{n+1} + c a_n = 0$ 的遞迴關係式，其**特徵方程式（Characteristic Equation）**為：
     $r^2 + b r + c = 0$
   • 若特徵方程式具有兩個相異實根 $r_1, r_2$（即判別式 $b^2 - 4c > 0$），則遞迴關係式的**通解（General Solution）**可表示為：
     $a_n = C_1 r_1^n + C_2 r_2^n$
     其中 $C_1, C_2$ 為由初始條件（如 $a_0, a_1$）所決定的常數。

---

解題方法

第一階段：求解未知係數 $b$ 與 $c$

已知遞迴關係式為 $a_{n+2} + b a_{n+1} + c a_n = 0$，且已知前幾項為 $a_0 = 0, a_1 = 2, a_2 = 6, a_3 = 56$。

1. 將 $n = 0$ 代入遞迴式：
   $a_2 + b a_1 + c a_0 = 0$
   代入 $a_0 = 0, a_1 = 2, a_2 = 6$：
   $6 + 2b + c(0) = 0 \implies 6 + 2b = 0 \implies b = -3$

2. 將 $n = 1$ 代入遞迴式：
   $a_3 + b a_2 + c a_1 = 0$
   代入 $a_1 = 2, a_2 = 6, a_3 = 56$ 及已求得之 $b = -3$：
   $56 + (-3)(6) + c(2) = 0$
   $56 - 18 + 2c = 0 \implies 38 + 2c = 0 \implies c = -19$

綜上所述，得常數係數為 $b = -3$、$c = -19$。故遞迴關係式確定為：
$a_{n+2} - 3a_{n+1} - 19a_n = 0$

---

第二階段：求解一般項 $a_n$

1. 列出特徵方程式：
   根據遞迴式 $a_{n+2} - 3a_{n+1} - 19a_n = 0$，其對應之特徵方程式為：
   $r^2 - 3r - 19 = 0$

2. 求解特徵根：
   使用一元二次方程式公式解 $r = \frac{-B \pm \sqrt{B^2 - 4AC}}{2A}$：
   $r = \frac{3 \pm \sqrt{(-3)^2 - 4(1)(-19)}}{2} = \frac{3 \pm \sqrt{9 + 76}}{2} = \frac{3 \pm \sqrt{85}}{2}$
   設兩相異特徵根分別為 $r_1 = \frac{3 + \sqrt{85}}{2}$ 與 $r_2 = \frac{3 - \sqrt{85}}{2}$。

3. 寫出通解形式：

核心觀念

本題旨在考驗考生對分治法（Divide-and-Conquer）代表性排序演算法——**快速排序法（Quick Sort）**的演算法步驟理解與時間複雜度之數學推導能力。

主要涵蓋以下核心觀念與定義：

1. 分治法三大步驟：
   • 分割（Divide）：選擇樞紐碼（Pivot），將陣列切分為小於等於與大於樞紐碼的兩個子陣列。
   • 克服（Conquer）：遞迴呼叫 Quick Sort 分別處理左右兩個子陣列。
   • 合併（Combine）：因原位（In-place）排序已完成，無需額外合併操作。
2. 時間複雜度遞迴關係式（Recurrence Relation）：
   • 根據樞紐碼切分位置之不同，建立最差狀況（Worst Case）、最佳狀況（Best Case）與平均狀況（Average Case）之遞迴關係式。
3. 遞迴關係式求解方法：
   • 代換法 / 反覆展開法（Expansion Method）
   • 主定理（Master Theorem）
   • 代數變數變換與伸縮連加法（Telescoping Method）

---

解題方法

(a) 快速排序法（Quick Sort）演算法詳細說明

Quick Sort 是一種基於分治法（Divide-and-Conquer）的原位（In-place）排序演算法。假設輸入陣列為 $A[p \ldots r]$，演算法詳細運作機制如下：

1. 演算法三大核心步驟

• Divide（分割）：選定一個元素作為樞紐碼 $x = A[r]$（以末項為例），呼叫 Partition(A, p, r) 進行重排，使得重排後存在一索引 $q$：
  • 對所有 $p \le k < q$，$A[k] \le x$
  • $A[q] = x$
  • 對所有 $q < k \le r$，$A[k] > x$
• Conquer（克服）：對左子陣列 $A[p \ldots q-1]$ 與右子陣列 $A[q+1 \ldots r]$ 遞迴呼叫 QuickSort。
• Combine（結合）：子陣列皆完成原位排序，不需執行任何額外動作。

2. 演算法虛擬碼（Pseudocode）

QuickSort(A, p, r)
1. if p < r
2.     q = Partition(A, p, r)
3.     QuickSort(A, p, q - 1)
4.     QuickSort(A, q + 1, r)

Partition(A, p, r)
1. x = A[r]             // 選擇最後一個元素為 Pivot
2. i = p - 1            // i 為小於等於 Pivot 之區域邊界
3. for j = p to r - 1
4.     if A[j] <= x
5.         i = i + 1
6.         swap A[i] with A[j]
7. swap A[i + 1] with A[r]
8. return i + 1

---

(b) 時間複雜度遞迴關係式推導

假設輸入資料大小為 $n = r - p + 1$。Partition 步驟需對長度為 $n$ 的陣列掃描一次，其時間複雜度為 $\Theta(n)$（設比較與移動代價為 $c \cdot n$，其中 $c > 0$ 為常數）。

遞迴關係式的通用型式為：
$T(n) = T(k) + T(n - 1 - k) + c \cdot n$
其中 $k$ 代表經 Partition 後左子陣列的元素個數（$0 \le k \le n-1$）。

1. 最差狀況（Worst Case）推導

• 發生條件：每次選取的樞紐碼皆為目前子陣列的最大值或最小值（例如：輸入資料已完全升冪或降冪排序），導致分割極度不平均，子陣列大小分別為 $0$ 與 $n-1$。
• 遞迴關係式：
  $T(n) = T(0) + T(n-1) + c \cdot n = T(n-1) + c \cdot n \quad (n > 1)$
  基本情況（Base Case）：$T(1) = \Theta(1)$。
• 數學推導（反覆展開法 Expansion Method）：

$$\begin{aligned} T(n) &= T(n-1) + c n \\ &= [T(n-2) + c(n-1)] + c n \\ &= T(n-3) + c(n-2) + c(n-1) + c n \\ &\ \ \vdots \\ &= T(1) + c \sum_{k=2}^{n} k \\ &= \Theta(1) + c \left[ \frac{n(n+1)}{2} - 1 \right] \\ &= \Theta(n^2) \end{aligned}$$

因此，最差時間複雜度為 $\Theta(n^2)$。

2. 最佳狀況（Best Case）推導

• 發生條件：每次選取的樞紐碼恰好將陣列平分為大小幾乎相等的兩半，即 $k \approx \frac{n-1}{2}$。
• 遞迴關係式：
  $T(n) = 2 T\left(\frac{n}{2}\right) + c \cdot n$
• 數學推導（主定理 Master Theorem）：
  對於遞迴式 $T(n) = a T(n/b) + f(n)$，此處 $a = 2, b = 2, f(n) = c n$。
  計算 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$。
  因為 $f(n) = \Theta(n) = \Theta(n^{\log_b a})$，符合主定理第二型（Case 2）：
  $T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)$
  因此，最佳時間複雜度為 $\Theta(n \log n)$。

3. 平均狀況（Average Case）推導

• 發生條件：假設所有可能的分割位置 $k \in \{0, 1, \dots, n-1\}$ 出現概率皆相等，即各為 $\frac{1}{n}$。
• 遞迴關係式：

核心觀念

本題旨在考驗離散領域中**樹狀結構（Tree Structure）**的基本計數定理與定義，主要涵蓋以下核心知識點：

1. 滿 $m$ 元樹（Full $m$-ary Tree）與高度（Height）之定義：

   • 一棵 $m$ 元樹中，若每個內部頂點（Internal Vertex）皆恰有 $m$ 個子節點，則稱為完整 $m$ 元樹（Complete $m$-ary Tree）。
   • 當所有葉節點（Leaves）皆位於相同的最高階層（Level $h$）時，此樹特稱為滿 $m$ 元樹（Full $m$-ary Tree）。
   • 根據標準定義（如 Rosen 離散數學），根節點（Root）部位於 Level $0$，高度為 $h$ 的滿 $m$ 元樹，其葉節點皆在 Level $h$。

2. 滿 $m$ 元樹的計數定理：
   設 $T$ 為高度 $h$ 之滿 $m$ 元樹：

   • ** Level $k$ 的頂點數**：$m^k$
   • 葉節點總數 $L$：$L = m^h$
   • 內部頂點總數 $i$：即非葉節點之總和（包含 Level $0$ 到 Level $h-1$）：
     $i = \sum_{k=0}^{h-1} m^k = 1 + m + m^2 + \dots + m^{h-1} = \frac{m^h - 1}{m - 1} = \frac{L - 1}{m - 1}$
   • 頂點總數 $n$：$n = i + L = \frac{m^{h+1} - 1}{m - 1}$，且滿足邊與頂點關係 $(m-1)i = L - 1$。

---

解題方法

根據題意，樹 $T$ 為一棵高度 $h = 7$ 且葉節點數 $L = 279,936$ 的滿 $m$ 元樹。解題步驟分為兩步：

步驟一：求出分支度 $m$

由滿 $m$ 元樹的性質可知，位於 Level $h=7$ 的葉節點數量公式為：
$L = m^h = m^7 = 279,936$