111 年 國立中山大學資訊管理學系碩士班甲組《離散數學》

因 $S$ 為含 $7$ 個相異正整數的集合，且每個元素至多為 $21$，故

$$\sum_{x\in S}x\le 15+16+\cdots+21=126.$$

$S$ 共有

$$2^7-1=127$$

核心觀念

本題考查計算理論（Theory of Computation）與離散數學中**有限狀態自動機（Finite State Machine / Deterministic Finite Automaton, DFA）**的建構與正規語言（Regular Language）的代數化簡。

1. 正規語言化簡（Language Simplification）：
   給定二元字母集 $I = \{0,1\}$，語言 $L = \{0,1\}^* \{11\} \cup \{0,1\}^* \{01\}$ 可利用代數提出共同後綴進行化簡：
   $L = \{0,1\}^* (\{11\} \cup \{01\}) = \{0,1\}^* (\{1\} \cup \{0\}) 1 = \{0,1\}^* \{0,1\} 1$
   化簡結果顯示，語言 $L$ 代表所有**「字串長度至少為 $2$，且最後一個字元為 $1$」**的二元字串集合（即結尾為 $01$ 或 $11$ 的字串）。

2. 狀態劃分與最簡 DFA（State Minimization）：
   依據 Myhill-Nerode 定理，辨識語言 $L$ 所需記憶的歷史資訊僅需劃分為 3 個不可相容的等價類（Equivalence Classes）：

   • 長度為 $0$ 的空字串 $\epsilon$。
   • 長度 $\ge 1$ 且目前不符合接受條件的字串（長度為 $1$ 的字串，或長度 $\ge 2$ 且以 $0$ 結尾的字串）。
   • 長度 $\ge 2$ 且以 $1$ 結尾的字串（接受狀態）。

---

解題方法

步驟一：語言特徵分析與狀態定義

根據語意將自動機劃分為 3 個狀態 $S = \{S_0, S_1, S_2\}$：

• $S_0$（初始狀態，非接受狀態）：代表系統初始狀態，尚未讀入任何字元（即讀入空字串 $\epsilon$）。
• $S_1$（中繼狀態，非接受狀態）：代表目前讀入的字串「長度 $\ge 1$ 且不屬於 $L$」。包含：
  1. 長度為 $1$ 的字串（"0" 或 "1"）。
  2. 長度 $\ge 2$ 且最後一個字元為 $0$ 的字串（如 "00", "10", "010" 等）。
• $S_2$（接受狀態，雙圈表示）：代表目前讀入的字串「長度 $\ge 2$ 且最後一個字元為 $1$」（即結尾為 $01$ 或 $11$ 的字串）。

步驟二：推導狀態轉移函數 $\delta(S, a)$

對每個狀態在接收輸入字元 $a \in \{0, 1\}$ 時進行推導：

1. 從狀態 $S_0$ 出發：

   • 讀入 $0$：字串變為 "0"（長度為 $1$），尚未達到接受條件，轉移至 $S_1$。
   • 讀入 $1$：字串變為 "1"（長度為 $1$），尚未達到接受條件，轉移至 $S_1$。

2. 從狀態 $S_1$ 出發：

   • 讀入 $0$：前導字串長度 $\ge 1$，接上 $0$ 後字串長度必 $\ge 2$ 且以 $0$ 結尾，不符合接受條件，維持在 $S_1$。
   • 讀入 $1$：前導字串長度 $\ge 1$，接上 $1$ 後字串長度必 $\ge 2$ 且以 $1$ 結尾（末兩位必為 $01$ 或 $11$），符合接受條件，轉移至 $S_2$。

3. 從狀態 $S_2$ 出發：

   • 讀入 $0$：原字串已在 $S_2$（長度 $\ge 2$ 且以 $1$ 結尾），接上 $0$ 後字串長度 $\ge 3$ 且最後一位變為 $0$（末兩位為 $10$），失去接受條件，轉移至 $S_1$。
   • 讀入 $1$：原字串已在 $S_2$，接上 $1$ 後字串長度 $\ge 3$ 且最後一位仍為 $1$（末兩位為 $11$），持續符合接受條件，維持在 $S_2$。

步驟三：狀態轉移表（State Transition Table）

目前狀態 $S$	輸入 $0$ 後轉移狀態 $\delta(S, 0)$	輸入 $1$ 後轉移狀態 $\delta(S, 1)$	是否為接受狀態
$\rightarrow S_0$	$S_1$	$S_1$	否
$S_1$	$S_1$	$S_2$	否
$*S_2$	$S_1$	$S_2$	是

註：$\rightarrow$ 表示初始狀態，$*$ 表示接受狀態。

步驟四：狀態圖（State Diagram）結構

狀態圖包含以下要素：

• 頂點（Nodes）：$S_0, S_1, S_2$ 三個圓圈，$S_2$ 為雙圈（Double Circle）。
• 初始邊（Initial Arrow）：由外部指向 $S_0$ 的邊。
• 有向邊與標籤（Directed Edges and Labels）：
  • $S_0 \xrightarrow{0, 1} S_1$
  • $S_1 \xrightarrow{0} S_1$ （自環, Self-loop）
  • $S_1 \xrightarrow{1} S_2$
  • $S_2 \xrightarrow{0} S_1$
  • $S_2 \xrightarrow{1} S_2$ （自環, Self-loop）

stateDiagram-v2
    [*] --> S0
    S0 --> S1 : 0, 1
    S1 --> S1 : 0
    S1 --> S2 : 1
    S2 --> S1 : 0
    S2 --> S2 : 1

---

選項分析

核心觀念

1. 質因數分解（Prime Factorization）：根據算術基本定理，任何大於 $1$ 的正整數 $n$ 均可唯一分解為質數乘積 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$。
2. 正因數的結構表示：$n$ 的任一正因數 $x$ 與 $y$ 皆可表示為各質因數指數次方之乘積：
   $x = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \quad 0 \le a_i \le e_i$
   $y = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}, \quad 0 \le b_i \le e_i$
3. 整除關係（Divisibility Relation）與指數不等式：在正因數集合 $A$ 上定義關係 $xRy \iff x \mid y$。在各質因數的指數維度上，整除關係可等價轉化為指數間的大小不等式條件：
   $x \mid y \iff a_i \le b_i \quad (\forall i \in \{1, 2, \dots, k\})$
4. 積法則（Product Rule）與組合計數：各質因數指數的選取彼此獨立。對於單一質因數 $p_i$ 的指數 $e_i$，滿足 $0 \le a_i \le b_i \le e_i$ 的整數對 $(a_i, b_i)$ 數量為：
   $\sum_{b_i=0}^{e_i} (b_i + 1) = \frac{(e_i + 1)(e_i + 2)}{2} = \binom{e_i + 2}{2} = H_2^{e_i+1}$
   關係 $R$ 中的有序對總數即為各質因數組合數之乘積：
   $|R| = \prod_{i=1}^{k} \frac{(e_i + 1)(e_i + 2)}{2}$

---

解題方法

Step 1：將 $n = 6680$ 進行質因數分解

將 $6680$ 進行質因數分解：
$6680 = 2 \times 3340 = 2^2 \times 1670 = 2^3 \times 835 = 2^3 \times 5^1 \times 167^1$
檢查 $167$ 是否為質數：$\sqrt{167} \approx 12.92$，檢驗小於 $12.92$ 的質數（$2, 3, 5, 7, 11$）：

• $167$ 不被 $2, 3, 5$ 整除；
• $167 \div 7 = 23 \dots 6$；
• $167 \div 11 = 15 \dots 2$。
  故 $167$ 為質數。
  得到 $n = 6680 = 2^3 \times 5^1 \times 167^1$。

Step 2：建立因數指數的整除條件

設 $A$ 為 $6680$ 的所有正因數所組成的集合。
任意兩因數 $x, y \in A$ 可寫成：
$x = 2^{a_1} \times 5^{a_2} \times 167^{a_3}, \quad 0 \le a_1 \le 3,\; 0 \le a_2 \le 1,\; 0 \le a_3 \le 1$
$y = 2^{b_1} \times 5^{b_2} \times 167^{b_3}, \quad 0 \le b_1 \le 3,\; 0 \le b_2 \le 1,\; 0 \le b_3 \le 1$
依據題目定義 $xRy \iff x \mid y$，其充分必要條件為：
$a_1 \le b_1 \quad \text{且} \quad a_2 \le b_2 \quad \text{且} \quad a_3 \le b_3$

Step 3：計算各質因數指數對 $(a_i, b_i)$ 的組合數

根據乘法原理，總有序對數量 $|R| = N_1 \times N_2 \times N_3$：

1. 質因數 $2$ 的指數部分（$e_1 = 3$）：
   需滿足 $0 \le a_1 \le b_1 \le 3$。
   • 若 $b_1 = 0$，則 $a_1 = 0$（$1$ 種）
   • 若 $b_1 = 1$，則 $a_1 \in \{0, 1\}$（$2$ 種）
   • 若 $b_1 = 2$，則 $a_1 \in \{0, 1, 2\}$（$3$ 種）

核心觀念

1. 迴文（Palindrome）的對稱定義
   長度為 $n$ 的序列 $S = (a_1, a_2, \dots, a_n)$ 若為迴文，當且僅當其滿足對稱條件：
   $a_i = a_{n+1-i} \quad \forall \, 1 \le i \le n$

2. 獨立自由度（Degrees of Freedom）
   由於對稱條件限制，後半段字元 $a_{\lceil n/2 \rceil + 1}, \dots, a_n$ 完全由前半段字元 $a_1, a_2, \dots, a_{\lceil n/2 \rceil}$ 唯一確定。因此，長度為 $n$ 的迴文僅有前 $\lceil n/2 \rceil$ 個位置具備獨立選擇的自由度。

3. 乘法原理（Multiplication Principle）與符號集大小
   題目給定 $1 \le t \le n$，表明符號集（Alphabet）的大小為 $n$（即 $\Sigma = \{1, 2, \dots, n\}$），且迴文的首個字元 $a_1$ 被固定為符號 $t$。

---

解題方法

步驟一：分析迴文自由位置

設迴文為 $S = (a_1, a_2, \dots, a_n)$，其中每個元素 $a_i \in \{1, 2, \dots, n\}$。
整串迴文由前 $\lceil n/2 \rceil$ 個位置完全決定：

• 當 $n$ 為偶數時：前 $\frac{n}{2}$ 個位置決定全串。
• 當 $n$ 為奇數時：前 $\frac{n+1}{2}$ 個位置（含正中間位置）決定全串。

步驟二：依題目限制計算各位置選擇數

1. 位置 $a_1$：題目限定開頭為 $t$，故 $a_1 = t$，僅有 $1$ 種選擇。
2. 位置 $a_n$：根據迴文對稱性 $a_n = a_1 = t$，僅有 $1$ 種選擇。
3. 位置 $a_2, a_3, \dots, a_{\lceil n/2 \rceil}$：共 $\lceil n/2 \rceil - 1$ 個獨立位置。每個位置皆可從符號集 $\{1, 2, \dots, n\}$ 中任意選取，各有 $n$ 種選擇。
4. 位置 $a_{\lceil n/2 \rceil + 1}, \dots, a_{n-1}$：由對稱關係 $a_{n+1-i} = a_i$ 自動決定，各有 $1$ 種選擇。

步驟三：運用乘法原理推導總數

將所有獨立位置的選擇數相乘：

$\text{迴文總數} = 1 \times \underbrace{n \times n \times \dots \times n}_{(\lceil n/2 \rceil - 1) \text{ 個}} = n^{\lceil n/2 \rceil - 1}$

依 $n$ 的奇偶性展開說明如下：

• 當 $n$ 為偶數時：
  $\text{自由位置數} = \frac{n}{2} - 1 = \frac{n-2}{2} \implies \text{迴文總數} = n^{\frac{n-2}{2}}$
• 當 $n$ 為奇數時：

每一序列等可能，共有 $3^{26}$ 種。利用奇偶篩選公式：

$$N_{\varepsilon_0,\varepsilon_1} =\frac14\sum_{x,y=\pm1}x^{\varepsilon_0}y^{\varepsilon_1}(x+y+1)^{26},$$

其中 $\varepsilon_i=0$ 表示偶數，$\varepsilon_i=1$ 表示奇數。

(a) 要求 $0$、$2$ 的個數皆為偶數：

$$N=\frac14\left(3^{26}+1^{26}+1^{26}+(-1)^{26}\right) =\frac{3^{26}+3}{4}.$$

因此

核心觀念

本題考查：

• 以「最後一個位元」或「第一個位元」分類計數。
• 將字串分成互斥且完備的情況，建立遞迴關係。
• 使用特徵方程式解二階線性遞迴。
• 費氏數列公式。

以下採用費氏數列定義：

$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\ge 2)$$

---

(a) 不含連續兩個 0 的二元字串

建立遞迴關係

令 $a_n$ 表示長度為 $n$、且不含連續 $0$ 的二元字串數量。

依照字串最後一個位元分類。

情況一：最後一個位元是 1

在任何符合條件的長度 $n-1$ 字串後面接上 $1$，一定不會產生連續的 $0$。

因此此類字串共有：

$$a_{n-1}$$

情況二：最後一個位元是 0

因為不能出現連續兩個 $0$，倒數第二個位元必須是 $1$。因此字串最後兩位固定為 $10$。

前面的長度 $n-2$ 部分只要是不含連續 $0$ 的合法字串即可，共有：

$$a_{n-2}$$

兩種情況互斥且涵蓋所有合法字串，所以：

$$a_n=a_{n-1}+a_{n-2}\qquad(n\ge 3)$$

初始條件

長度為 $1$ 的字串為 $0,1$，共有：

$$a_1=2$$

長度為 $2$ 的合法字串為：

$$01,\quad 10,\quad 11$$

因此：

$$a_2=3$$

故遞迴關係為：

$$\boxed{a_n=a_{n-1}+a_{n-2}\quad(n\ge 3),\qquad a_1=2,\ a_2=3}$$

求閉合解

遞迴式的特徵方程式為：

$$r^2=r+1$$

即：

$$r^2-r-1=0$$

兩根為：

$$r_1=\frac{1+\sqrt{5}}{2},\qquad r_2=\frac{1-\sqrt{5}}{2}$$

因此通解為：

$$a_n=C_1r_1^n+C_2r_2^n$$

由於 $a_n$ 與費氏數列前幾項相同：

$$a_1=2=F_3,\qquad a_2=3=F_4$$

所以：

$$a_n=F_{n+2}$$

使用 Binet 公式：

$$F_k=\frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^k - \left(\frac{1-\sqrt{5}}{2}\right)^k \right]$$

可得：

$$\boxed{ a_n= \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+2} \right] }$$

---

(b) 不含連續兩個 1，且最後一位為 0 的二元字串

建立遞迴關係

令 $b_n$ 表示長度為 $n$、不含連續 $1$，且最後一位是 $0$ 的二元字串數量。

本題依照字串的第一個位元分類。

情況一：第一個位元是 0

依遞迴式

$$p_n=p_{n-1}(0.3)^{p_{n-2}},\qquad p_0=0,\ p_1=1$$

逐項計算至首次低於 $0.01$：

核心觀念

本題屬於組合數學（Combinatorics）中典型的**「相異物放入相異箱」**（Distinguishable objects into distinguishable containers）分配問題。相關定義與定理如下：

1. 乘法原理（Rule of Product）：若完成某項工作需分次執行 $k$ 個互相獨立的步驟，且第 1 個步驟有 $n_1$ 種選擇、第 2 個步驟有 $n_2$ 種選擇……第 $k$ 個步驟有 $n_k$ 種選擇，則完成該項工作的總方法數為：
   $n_1 \times n_2 \times \dots \times n_k$
2. 相異物分配與函數總數：將 $m$ 個相異元素分配至 $n$ 個相異容器（無容量限制），等同於建立一個從大小為 $m$ 的定義域映至大小為 $n$ 的對應域之函數。其總方法數即為 $n^m$。

---

解題方法

1. 分析題目已知條件：

   • 彈珠（分配對象）：共有 20 顆。雖然尺寸相同（same size），但因為「每顆彈珠顏色皆不相同」（each marble is a different color），故 20 顆彈珠為相異物。
   • 罐子（容器）：共有 6 個相異罐子（six distinct jars），故罐子為相異物。
   • 容量限制：題目未對罐子容量設限，每個罐子皆可裝入 0 至 20 顆彈珠。

2. 推導關鍵步驟：

   • 考慮將 20 顆相異彈珠依次放入罐子中，每顆彈珠的放置動作均為獨立決策：
     • 第 1 顆彈珠：可任意選擇 6 個罐子中的 1 個，共有 6 種選擇。
     • 第 2 顆彈珠：可任意選擇 6 個罐子中的 1 個，共有 6 種選擇。
     • 依此類推，直致第 20 顆彈珠，同樣有 6 種選擇。
   • 根據乘法原理，總分配方法數為：
     $\underbrace{6 \times 6 \times \dots \times 6}_{20 \text{ 個 } 6} = 6^{20}$

---

選項分析

本題為計算填充題。為幫助考生釐清離散數學中常見的排組易混淆形式，以下針對正確與常見錯誤算式進行逐一分析：