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

核心觀念

本題考查離散數學中**組合數學（Combinatorics）的核心主題：重複組合（Combinations with Repetition / Multiset Combinations）與分類計數原理（Rule of Sum），亦可採用生成函數（Generating Function）**進行解答。

1. 重複組合公式：
   將 $n$ 個相同的物體分給 $k$ 個不同的容器，允許容器為空（即求方程式 $x_1 + x_2 + \dots + x_k = n$ 之非負整數解個數），方法數為：
   $H^k_n = C(n + k - 1, n) = C(n + k - 1, k - 1)$
   特別地，當 $k = 2$ 時，$H^2_n = C(n + 1, 1) = n + 1$。

2. 分類計數原理：
   若一事件的完成可劃分為若干個互斥（Disjoint）的情況，則總方法數等於各個情況之方法數相加。

---

解題方法

【數學模型建立】
設三個相異桶子分別為 $B_1, B_2, B_3$，其所分配到的白色顆粒數分別為 $x_1, x_2, x_3$。
依題意，求下列不定方程式之非負整數解個數：
$x_1 + x_2 + x_3 = 9$
條件限制：

• $x_1, x_2 \ge 0$ 且為整數
• $x_3 \ge 0$ 且 $x_3$ 為偶數（$x_3 \in \{0, 2, 4, 6, 8\}$）

---

【詳細推導步驟：分類討論法】

根據 $x_3$ 的可能偶數值進行分情況討論（$x_3 = 2k$，$k = 0, 1, 2, 3, 4$）：

1. 情況一：當 $x_3 = 0$ 時
   方程式簡化為 $x_1 + x_2 = 9$
   方法數為：
   $H^2_9 = C(9 + 2 - 1, 9) = C(10, 9) = 10 \text{ 種}$

2. 情況二：當 $x_3 = 2$ 時
   方程式簡化為 $x_1 + x_2 = 7$
   方法數為：
   $H^2_7 = C(7 + 2 - 1, 7) = C(8, 7) = 8 \text{ 種}$

3. 情況三：當 $x_3 = 4$ 時
   方程式簡化為 $x_1 + x_2 = 5$
   方法數為：
   $H^2_5 = C(5 + 2 - 1, 5) = C(6, 5) = 6 \text{ 種}$

4. 情況四：當 $x_3 = 6$ 時
   方程式簡化為 $x_1 + x_2 = 3$
   方法數為：
   $H^2_3 = C(3 + 2 - 1, 3) = C(4, 3) = 4 \text{ 種}$

5. 情況五：當 $x_3 = 8$ 時
   方程式簡化為 $x_1 + x_2 = 1$
   方法數為：
   $H^2_1 = C(1 + 2 - 1, 1) = C(2, 1) = 2 \text{ 種}$

核心觀念

本題考驗計數原理（Counting Principle）、整數的位值展開（Place-Value Expansion）與有限級數求和（Summation of Series）。

1. 三位數回文數的結構：
   三位數由百位、$10^1$ 位（十位）與 $10^0$ 位（個位）組成。回文數（Palindrome）代表從左至右與從右至左讀皆相同。因此，三位數回文數可表示為：
   $N = aba = 100a + 10b + a = 101a + 10b$
   其中 $a$ 為百位與個位數字，$b$ 為十位數字。

2. 變數取值範圍與計數：
   題目限定數字範圍在 $200$ 至 $999$ 之間：

   • 百位與個位數字：$a \in \{2, 3, 4, 5, 6, 7, 8, 9\}$，共 $8$ 種可能。
   • 十位數字：$b \in \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$，共 $10$ 種可能。
   • 根據乘法原理，滿足條件的三位數回文數共有 $8 \times 10 = 80$ 個。

---

解題方法

求解所有回文數之和時，採用位值分離求和法，將百位、個位與十位所產生的數值分開統計。

步驟一：建立總和數學式

設所求之總和為 $S$：
$S = \sum_{a=2}^{9} \sum_{b=0}^{9} (101a + 10b)$

根據加法拆項與線性性質，將式子分成「$a$ 項的貢獻」與「$b$ 項的貢獻」：
$S = \sum_{a=2}^{9} \sum_{b=0}^{9} 101a + \sum_{a=2}^{9} \sum_{b=0}^{9} 10b$

步驟二：計算百位與個位的總貢獻（$101a$ 部分）

對每一個特定的 $a$，十位數字 $b$ 有 $10$ 種變化（$0$ 到 $9$）：
$\sum_{a=2}^{9} \sum_{b=0}^{9} 101a = \sum_{a=2}^{9} (10 \times 101a) = 1010 \times \sum_{a=2}^{9} a$

計算 $a$ 的累加和：

核心觀念

本題旨在考察數論（Number Theory）中的基礎核心定理——歐幾里得質數無限性定理（Euclid's Theorem on the Infinitude of Primes）。解答本題需掌握以下邏輯概念與定義：

1. 反證法（Proof by Contradiction）：先假設欲證命題的反面成立，經由嚴密的邏輯推導導出矛盾，從而證明原命題為真。
2. 算術基本定理（Fundamental Theorem of Arithmetic）：任何大於 $1$ 的正整數，要麼本身是質數，要麼可以唯一分解為若干個質數的乘積。換言之，任意大於 $1$ 的整數 $N$ 必存在至少一個質因數（Prime Factor）。
3. 整除的線性組合性質（Divisibility Properties）：若整數 $d$ 同時整除 $a$ 與 $b$（即 $d \mid a$ 且 $d \mid b$），則對於任意整數 $x, y$， $d$ 亦必整除 $ax + by$。特別地，若 $d \mid a$ 且 $d \mid (a - 1)$，則 $d \mid (a - (a - 1)) \implies d \mid 1$。

---

解題方法

採用經典的歐幾里得反證法（Euclid's Proof by Contradiction），推導步驟如下：

Step 1: 建立反證假設

假設質數的數量是有限的，設共有 $n$ 個質數，並將所有質數按順序排列，組成有限集合：
$P = \{p_1, p_2, p_3, \dots, p_n\}$
其中 $p_1 = 2, p_2 = 3, p_3 = 5, \dots$，$p_n$ 為假設中最大的質數。

Step 2: 構造關鍵整數

構造一個正整數 $N$，定義為所有已知質數之乘積再加上 $1$：
$N = (p_1 \cdot p_2 \cdot p_3 \cdots p_n) + 1 = \left( \prod_{i=1}^{n} p_i \right) + 1$
由於 $p_1 = 2$，故 $N \ge 2 + 1 = 3 > 1$。

Step 3: 利用算術基本定理尋找質因數

根據算術基本定理，由於 $N > 1$，$N$ 必存在至少一個質因數，記作 $q$。

核心觀念

1. 模逆元（Modular Multiplicative Inverse）：
   若整數 $a$ 與 $b$ 互質（即 $\gcd(a, b) = 1$），則存在整數 $x$ 使得 $ax \equiv 1 \pmod b$。稱 $x$ 為 $a$ 在 modulo $b$ 下的模逆元，記作 $a^{-1} \pmod b$。
2. 貝祖定理（Bézout's Identity）：
   對於任意整數 $a, b$，其最大公因數 $c = \gcd(a, b)$ 可表示為 $a$ 與 $b$ 的整數線性組合，即存在整數 $x, y$ 使得 $ax + by = c$。當 $a, b$ 互質時，$\gcd(a, b) = 1$，式子簡化為 $ax + by = 1$。
3. 擴展歐幾里得演算法（Extended Euclidean Algorithm）：
   在執行歐幾里得演算法（輾轉相除法）求 $\gcd(a, b)$ 的過程中，記錄每一步的商數與餘數，並藉由「反向回代（Backward Substitution）」將最大公因數 $1$ 表達為 $a$ 與 $b$ 的整數線性組合，從而求出係數 $x$ 與 $y$。

---

解題方法

1. 理論推導與切入點

已知 $a$ 與 $b$ 互質，即 $\gcd(a, b) = 1$。由貝祖定理可知，存在整數 $x, y$ 滿足線性方程式：
$ax + by = 1$

對此方程式兩邊同時取 modulo $b$ 同餘運算：
$(ax + by) \pmod b = 1 \pmod b$

因為 $by$ 是 $b$ 的整倍數，在 modulo $b$ 下 $by \equiv 0 \pmod b$，故上式可簡化為：
$ax \equiv 1 \pmod b$

由模逆元的定義 $a \cdot a^{-1} \equiv 1 \pmod b$，可直接對應得出：貝祖等式中 $a$ 的線性係數 $x$ 即為 $a$ 在 modulo $b$ 下的模逆元 $a^{-1}$。

2. 使用歐幾里得演算法求 $a^{-1}$ 之關鍵步驟

【步驟一】正向執行歐幾里得演算法（輾轉相除法）
設 $r_0 = a, r_1 = b$，進行連續帶餘除法直到餘數為 $0$：
$r_0 = q_1 \cdot r_1 + r_2 \quad (0 < r_2 < r_1)$
$r_1 = q_2 \cdot r_2 + r_3 \quad (0 < r_3 < r_2)$
$\vdots$
$r_{k-2} = q_{k-1} \cdot r_{k-1} + r_k \quad (\text{其中 } r_k = \gcd(a, b) = 1)$
$r_{k-1} = q_k \cdot r_k + 0$

【步驟二】反向回代（Backward Substitution）
從最後一步非零餘數 $r_k = 1$ 開始倒推，依次將餘數替換為前兩項的組合：

1. 改寫倒數第二式：$1 = r_k = r_{k-2} - q_{k-1} \cdot r_{k-1}$。
2. 將前一步的餘數 $r_{k-1}, r_{k-2}, \dots$ 逐步代入並合併同類項。
3. 最終整理成 $1 = a x + b y$ 的形式，求出整數解 $(x, y)$。

【步驟三】模逆元範圍調整
係數 $x$ 即為所求。若計算出的 $x < 0$ 或 $x \ge b$，則取：
$a^{-1} = (x \bmod b + b) \bmod b$
確保模逆元落在標準餘數系 $\{0, 1, 2, \dots, b-1\}$ 中。

核心觀念

本題考查的核心觀念包含以下三點：

1. 算術基本定理（Prime Factorization）：任一大於 $1$ 的自然數皆可唯一分解為質數的乘積。將目標數值進行質因數分解，是分析因數結構的第一步。
2. 無序因子分解（Unordered Factorization）：將一正整數 $N$ 表示成 $k$ 個大於 $1$ 的正整數相乘 $N = a_1 \times a_2 \times \dots \times a_k$，其中 $a_i > 1$。由於是「無序（unordered）」，因子的排列順序不計，例如 $a \times b \times c$ 與 $b \times a \times c$ 視為相同的分解方式。
3. 第二類斯特林數（Stirling Numbers of the Second Kind, $S(n, k)$ 或 $\left\{ \begin{matrix} n \\ k \end{matrix} \right\}$）：定義為將包含 $n$ 個相異元素的集合，劃分成 $k$ 個「非空且無順序」子集的方案數。當一正整數 $N$ 可以分解成 $n$ 個互不相同的質因子乘積時（即無平方因子數 Square-free number），將 $N$ 分解為 $k$ 個均大於 $1$ 的無序因子的方案數，正好等價於將這 $n$ 個相異質因子分配到 $k$ 個非空子集中，其方法數即為 $S(n, k)$。

---

解題方法

步驟一：對 389,298 進行質因數分解

首先對 $N = 389,298$ 進行質因數分解：
$389,298 = 2 \times 3 \times 7 \times 13 \times 23 \times 31$
可知 $N$ 為 $6$ 個互不相同的質數之乘積（$n = 6$）。

步驟二：建立與集合分割的對應關係

設 $S = \{2, 3, 7, 13, 23, 31\}$ 為 $N$ 的質因子集合，其元素個數 $|S| = 6$。
題目要求將 $N$ 分解為 $3$ 個均大於 $1$ 的無序因子相乘（即 $N = a \times b \times c$ 且 $a, b, c > 1$）：

• 由於每個因子均大於 $1$，代表每個因子至少包含 $S$ 中的一個質因子。
• 由於 $N$ 無重複的質因子，將 $S$ 劃分成 $3$ 個非空相異子集 $S_1, S_2, S_3$，各自元素連乘積即分別對應到 $a, b, c$。
• 因子順序不影響結果（unordered factorization），因此與子集的順序無關。

故將 $389,298$ 分解為 $3$ 個大於 $1$ 的無序因子之方案數，等價於將 $6$ 個相異元素劃分為 $3$ 個非空子集的方案數，即求第二類斯特林數 $S(6, 3)$。

步驟三：計算第二類斯特林數 $S(6, 3)$

解法一：通用公式（取斥原理）計算
第二類斯特林數的求值公式為：
$S(n, k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$
代入 $n = 6, k = 3$：

核心觀念

本題旨在考驗近世代數／代數結構（Algebraic Structures）中**閉合二元運算（Closed Binary Operation）**的 基本性質判定：

1. 閉合二元運算（Closed Binary Operation）：
   對集合 $\mathbb{Z}$ 上的二元運算 $f: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$，意即對任意 $x, y \in \mathbb{Z}$，映射結果 $f(x, y)$ 均落回整數集合 $\mathbb{Z}$ 中。
2. 交換律（Commutative Property）：
   若對所有 $x, y \in \mathbb{Z}$，均滿足 $f(x, y) = f(y, x)$，則稱 $f$ 滿足交換律。若欲證明不滿足交換律，只需舉出一組反例 $(x_0, y_0) \in \mathbb{Z} \times \mathbb{Z}$ 使得 $f(x_0, y_0) \neq f(y_0, x_0)$。
3. 結合律（Associative Property）：
   若對所有 $x, y, z \in \mathbb{Z}$，均滿足 $f(f(x, y), z) = f(x, f(y, z))$，則稱 $f$ 滿足結合律。若欲證明不滿足結合律，只需舉出一組反例 $(x_0, y_0, z_0) \in \mathbb{Z}^3$ 使得 $f(f(x_0, y_0), z_0) \neq f(x_0, f(y_0, z_0))$。

---

解題方法

判定二元運算是否滿足交換律或結合律時，標準解題流程如下：

• 證明成立：必須進行一般性的代數符號展開與化簡，證明對任意變數等式恆成立。
• 證明不成立：可經由代數展開發現對應項係數不對稱，並進一步選擇適當且計算簡單的整數（如 $0, 1, 2$）構造出明確的具體反例（Counterexample）。

---

各小題代數推導與分析

(a) $f(x, y) = 7x + 17y - 119xy$

1. 交換律檢驗

• 代數分析：
  $f(x, y) = 7x + 17y - 119xy$
  $f(y, x) = 7y + 17x - 119yx = 17x + 7y - 119xy$
  兩式相減：$f(x, y) - f(y, x) = 10(y - x)$。當 $x \neq y$ 時，該值不為 $0$，故代數結構非對稱。
• 具體反例：取 $x = 1, y = 0$：
  $f(1, 0) = 7(1) + 17(0) - 119(1)(0) = 7$
  $f(0, 1) = 7(0) + 17(1) - 119(0)(1) = 17$
  因為 $f(1, 0) = 7 \neq 17 = f(0, 1)$，故 $f$ 不滿足交換律。

2. 結合律檢驗

• 代數分析：
  計算左式 $f(f(x, y), z)$：令 $A = f(x, y) = 7x + 17y - 119xy$
  $f(A, z) = 7A + 17z - 119Az$
  $= 7(7x + 17y - 119xy) + 17z - 119(7x + 17y - 119xy)z$
  $= 49x + 119y - 833xy + 17z - 833xz - 2023yz + 14161xyz$

  計算右式 $f(x, f(y, z))$：令 $B = f(y, z) = 7y + 17z - 119yz$
  $f(x, B) = 7x + 17B - 119xB$
  $= 7x + 17(7y + 17z - 119yz) - 119x(7y + 17z - 119yz)$
  $= 7x + 119y + 289z - 833xy - 2023xz - 2023yz + 14161xyz$

  比較左式與右式之多項式係數，左式 $x$ 項係數為 $49$，右式 $x$ 項係數為 $7$；左式 $z$ 項係數為 $17$，右式 $z$ 項係數為 $289$，兩者顯然不相等。

• 具體反例：取 $x = 1, y = 0, z = 0$：
  $f(1, 0) = 7$
  $f(f(1, 0), 0) = f(7, 0) = 7(7) + 17(0) - 119(7)(0) = 49$
  另一方面：
  $f(0, 0) = 7(0) + 17(0) - 119(0)(0) = 0$
  $f(1, f(0, 0)) = f(1, 0) = 7$
  因為 $f(f(1, 0), 0) = 49 \neq 7 = f(1, f(0, 0))$，故 $f$ 不滿足結合律。

---

對稱關係若包含非對角序對 $(a,b)$，必須同時包含 $(b,a)$，故每組相異元素貢獻 $2$ 個序對；對角序對 $(a,a)$ 則各貢獻 $1$ 個。

集合 $A$ 有 $6$ 個對角序對及 $\binom{6}{2}=15$ 組非對角對稱序對。

(a) 恰有 $3$ 個序對：

以每 $50$ 本為一包，共有

$$\frac{2800}{50}=56\text{ 包}.$$

每組至少 $4$ 包、至多 $12$ 包。若每組先分配上限 $12$ 包，共 $60$ 包，故須從各組合計扣除 $4$ 包。

設第 $i$ 組扣除 $y_i$ 包，則

核心觀念

本題考查離散數學中**二階齊次常係數線性遞迴關係式（Second-Order Homogeneous Linear Recurrence Relation with Constant Coefficients）**的求解。解題關鍵包含以下數學概念：

1. 特徵方程式（Characteristic Equation）與複數共軛根：
   對於遞迴關係式 $a_{n+2} + A a_{n+1} + B a_n = 0$，其特徵方程式為 $r^2 + Ar + B = 0$。當特徵根為一對共軛複數 $r = \alpha \pm \beta i$ 時，可轉為極座標形式 $r = R(\cos\theta \pm i\sin\theta)$，其中模長 $R = \sqrt{\alpha^2 + \beta^2}$，輻角 $\theta = \tan^{-1}\left(\frac{\beta}{\alpha}\right)$。

2. 實數三角函數通解公式：
   若特徵根為共軛複數，則齊次解的實數形式通解可表示為：
   $a_n = R^n \left( C_1 \cos(n\theta) + C_2 \sin(n\theta) \right)$

3. 初始條件與待定係數：
   將給定的初始條件 $a_0, a_1$ 代入通解，建立聯立方程式以求得未知常數 $C_1, C_2$。

---

解題方法

步驟一：建立特徵方程式並求特徵根

設遞迴解的形式為 $a_n = r^n$，代入原遞迴關係式 $a_{n+2} + a_n = 0$：
$r^{n+2} + r^n = 0 \implies r^n(r^2 + 1) = 0$

因 $r \neq 0$，得特徵方程式為：
$r^2 + 1 = 0 \implies r^2 = -1$

解出特徵根為共軛複數：
$r = \pm i$

步驟二：轉換為極座標形式

將虛數單位 $r = \pm i$ 寫成複數極座標形式 $r = R(\cos\theta \pm i\sin\theta)$：

• 模長 $R = |i| = \sqrt{0^2 + 1^2} = 1$
• 輻角 $\theta = \frac{\pi}{2}$

步驟三：寫出通解結構

根據複數共軛根的齊次通解公式，寫出數列 $a_n$ 的實數三角形式通解：
$a_n = 1^n \left( C_1 \cos\left(\frac{n\pi}{2}\right) + C_2 \sin\left(\frac{n\pi}{2}\right) \right) = C_1 \cos\left(\frac{n\pi}{2}\right) + C_2 \sin\left(\frac{n\pi}{2}\right)$

步驟四：代入初始條件求解待定係數

已知初始條件為 $a_0 = 1$ 與 $a_1 = 5$：

1. 當 $n = 0$ 時：
   $a_0 = C_1 \cos(0) + C_2 \sin(0) = C_1 \cdot 1 + C_2 \cdot 0 = C_1 = 1$

2. 當 $n = 1$ 時：
   $a_1 = C_1 \cos\left(\frac{\pi}{2}\right) + C_2 \sin\left(\frac{\pi}{2}\right) = C_1 \cdot 0 + C_2 \cdot 1 = C_2 = 5$

得未知常數為 $C_1 = 1$，$C_2 = 5$。

步驟五：導出封閉形式解（Closed-form Solution）

將 $C_1, C_2$ 代回通解，即得到數列 $a_n$ 之特解：

核心觀念

本題考查離散數學中利用**普通生成函數（Ordinary Generating Function, OGF）**求解齊次線性遞迴關係（Linear Homogeneous Recurrence Relation）的標準程序。涉及的關鍵概念與公式包括：

1. 普通生成函數定義：
   序列 $\{a_n\}_{n=0}^{\infty}$ 的普通生成函數定義為：
   $A(x) = \sum_{n=0}^{\infty} a_n x^n = a_0 + a_1 x + a_2 x^2 + \dots$

2. 遞迴式的級數轉換：

   • $\sum_{n=0}^{\infty} a_{n+1} x^n = \frac{A(x) - a_0}{x}$
   • $\sum_{n=0}^{\infty} a_{n+2} x^n = \frac{A(x) - a_0 - a_1 x}{x^2}$

3. 部分分式拆解（Partial Fraction Decomposition）與無窮等比級數展開：
   將生成函數寫成部分分式後，利用泰勒級數（無窮等比級數）展開：
   $\frac{1}{1 - cx} = \sum_{n=0}^{\infty} c^n x^n$
   藉由比對 $x^n$ 的係數，即可導出 $a_n$ 的通項封閉解（Closed-form Solution）。

---

解題方法

步驟一：設定生成函數
設序列 $\{a_n\}$ 的普通生成函數為 $A(x) = \sum_{n=0}^{\infty} a_n x^n$。

步驟二：將遞迴關係轉換為生成函數方程式
已知遞迴關係為：
$a_{n+2} - 8a_{n+1} + 15a_n = 0, \quad n \ge 0$

將上式同乘以 $x^n$ 並對所有 $n \ge 0$ 求和：
$\sum_{n=0}^{\infty} a_{n+2} x^n - 8 \sum_{n=0}^{\infty} a_{n+1} x^n + 15 \sum_{n=0}^{\infty} a_n x^n = 0$

利用平移性質將各項以 $A(x)$ 表示：
$\frac{A(x) - a_0 - a_1 x}{x^2} - 8 \cdot \frac{A(x) - a_0}{x} + 15 A(x) = 0$

同乘以 $x^2$ 整理得：
$(A(x) - a_0 - a_1 x) - 8x(A(x) - a_0) + 15x^2 A(x) = 0$
$(1 - 8x + 15x^2) A(x) - a_0 + (8a_0 - a_1) x = 0$

步驟三：代入初始條件求解 $A(x)$
代入初始條件 $a_0 = 1$ 與 $a_1 = 6$：
$(1 - 8x + 15x^2) A(x) - 1 + (8(1) - 6) x = 0$
$(1 - 8x + 15x^2) A(x) - 1 + 2x = 0$
$(1 - 8x + 15x^2) A(x) = 1 - 2x$

因式分解分母 $1 - 8x + 15x^2 = (1 - 3x)(1 - 5x)$，解得：
$A(x) = \frac{1 - 2x}{(1 - 3x)(1 - 5x)}$

步驟四：部分分式拆解
設：
$A(x) = \frac{1 - 2x}{(1 - 3x)(1 - 5x)} = \frac{C_1}{1 - 3x} + \frac{C_2}{1 - 5x}$

利用重疊法（Heaviside Cover-up Method）求未知係數 $C_1, C_2$：