112 年 國立中央大學資訊工程學系軟體工程碩士班《離散數學與線性代數》

核心觀念

設集合 $V = \{1, 2, 3, 4, 5, 6\}$，二元關係（Binary Relation）$R \subseteq V \times V$ 由關聯矩陣（Relation Matrix）$\mathbf{A} = [a_{ij}]_{6 \times 6}$ 表示，其中：

$$a_{ij} = \begin{cases} 1, & \text{若 } (i, j) \in R \\ 0, & \text{若 } (i, j) \notin R \end{cases}$$

各二元關係之定義與矩陣等價性質如下：

1. 反身性（Reflexive）：
   對所有 $x \in V$，均有 $(x, x) \in R$。
   • 矩陣特徵：主對角線元素全為 1（即對所有 $i$，$a_{ii} = 1$）。
2. 反對稱性（Anti-symmetric）：
   對所有 $x, y \in V$，若 $(x, y) \in R$ 且 $(y, x) \in R$，則 $x = y$；等價於：當 $x \neq y$ 時，若 $(x, y) \in R$，則 $(y, x) \notin R$。
   • 矩陣特徵：對所有 $i \neq j$，$a_{ij}$ 與 $a_{ji}$ 不能同時為 1（即 $a_{ij} \cdot a_{ji} = 0$）。
3. 遞移性（Transitive）：
   對所有 $x, y, z \in V$，若 $(x, y) \in R$ 且 $(y, z) \in R$，則 $(x, z) \in R$。
   • 矩陣特徵：布林矩陣乘積滿足 $\mathbf{A} \odot \mathbf{A} \le \mathbf{A}$（即若 $[\mathbf{A}^2]_{ij} > 0$，則必定 $a_{ij} = 1$）。
4. 偏序關係（Partial Ordering Relation, Poset）：
   關係 $R$ 必須同時滿足反身性（Reflexive）、反對稱性（Anti-symmetric）與遞移性（Transitive）。
5. 對稱閉包（Symmetric Closure）：
   $R$ 的對稱閉包記為 $R_s = R \cup R^{-1}$。
   • 矩陣表示為 $\mathbf{M}_{R_s} = \mathbf{A} \vee \mathbf{A}^T$。

---

解題方法

由題幹給定之關聯矩陣 $\mathbf{A}$，列出關係 $R$ 的所有有序對（Ordered Pairs）：

$$R = \{(1, 6), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5), (6, 6)\}$$

透過矩陣結構與元素性質，逐一檢驗各選項之性質。

---

選項分析

• (A) 錯誤。
  反身性要求對角線元素 $a_{ii} = 1$ 對所有 $i \in \{1, 2, 3, 4, 5, 6\}$ 皆成立。
  檢視矩陣 $\mathbf{A}$ 的主對角線：

  $$(a_{11}, a_{22}, a_{33}, a_{44}, a_{55}, a_{66}) = (0, 0, 0, 1, 0, 1)$$

  例如 $(1, 1) \notin R$ 且 $(2, 2) \notin R$，因此 $R$ 不具反身性。

• (B) 正確。
  反對稱性要求對所有非對角線位置 $i \neq j$，若 $a_{ij} = 1$ 則必須 $a_{ji} = 0$。
  檢驗所有 $a_{ij} = 1$ 的非對角線元素對稱位置：

  • $a_{16} = 1 \implies a_{61} = 0$
  • $a_{23} = 1 \implies a_{32} = 0$

核心觀念

設集合 $V = \{1, 2, 3, 4, 5, 6\}$，關係 $R$ 由關係矩陣 $\mathbf{A} = [a_{ij}]$ 給定，其中 $a_{ij} = 1$ 代表 $(i, j) \in R$。
本題主要測驗「二元關係（Binary Relation）」的各種閉包（Closure）與關係性質：

1. 反身閉包（Reflexive Closure）$r(R)$：
   • 定義：包含 $R$ 的最小反身關係，$r(R) = R \cup \{(x, x) \mid x \in V\}$。
   • 矩陣特徵：對角線元素全為 1（即 $\mathbf{M}_{r(R)} = \mathbf{A} \lor \mathbf{I}$）。
2. 對稱閉包（Symmetric Closure）$s(R)$：
   • 定義：包含 $R$ 的最小對稱關係，$s(R) = R \cup R^{-1}$。
   • 矩陣特徵：矩陣需為對稱矩陣（即 $\mathbf{M}_{s(R)} = \mathbf{A} \lor \mathbf{A}^T$）。若 $(i, j) \in R$ 且 $(j, i) \notin R$，則必須補入 $(j, i)$。
3. 遞移閉包（Transitive Closure）$t(R)$：
   • 定義：包含 $R$ 的最小遞移關係，$t(R) = R \cup R^2 \cup R^3 \cup \dots = R^+$。
   • 圖論視角：在關係的有向圖（directed graph）中，只要頂點 $u$ 到頂點 $v$ 存在長度 $\ge 1$ 的有向路徑，則 $(u, v) \in t(R)$。
4. 偏序集（Partial Ordering Set, Poset）：
   • 關係必須滿足：反身性（Reflexive）、反對稱性（Antisymmetric）、遞移性（Transitive）。
5. 等價關係（Equivalence Relation）：
   • 關係必須滿足：反身性（Reflexive）、對稱性（Symmetric）、遞移性（Transitive）。

---

解題方法

由給定矩陣 $\mathbf{A}$ 列出關係 $R$ 的所有有序對（即矩陣中值為 1 的位置）：

$$R = \{(1, 6), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 4), (4, 5), (6, 6)\}$$

共有 9 個有序對。

1. 反身閉包 $r(R)$ 的建構：

反身性要求對角線元素 $(i, i) \in r(R)$，對所有 $i \in \{1, 2, 3, 4, 5, 6\}$。

• 原矩陣對角線上已有：$(4, 4)$ 與 $(6, 6)$（共 2 個 '1'）。
• 缺少的對角線元素為：$(1, 1), (2, 2), (3, 3), (5, 5)$。
• 因此，需額外加入 $6 - 2 = 4$ 個 '1'。

2. 對稱閉包 $s(R)$ 的建構：

對稱性要求若 $(i, j) \in R$ 且 $i \neq j$，則必須有 $(j, i)$。
原關係中 $i \neq j$ 的邊共有：

• $(1, 6) \in R \implies$ 需補 $(6, 1)$。
• $(2, 3) \in R \implies$ 需補 $(3, 2)$。
• $(2, 4) \in R \implies$ 需補 $(4, 2)$。
• $(2, 5) \in R \implies$ 需補 $(5, 2)$。
• $(3, 4) \in R \implies$ 需補 $(4, 3)$。
• $(3, 5) \in R \implies$ 需補 $(5, 3)$。
• $(4, 5) \in R \implies$ 需補 $(5, 4)$。

原矩陣中所有非對角線上的 1 皆無對稱邊對應（即對稱位置全為 0），共 7 個非對角線有序對。因此，需額外補入 7 個 '1'。

3. 遞移閉包 $t(R)$ 的建構：

分析有向圖中可到達的有向路徑：

• 節點 1：只有 $(1, 6)$，而 6 只有自環 $(6, 6)$，故可到達點為 $\{6\}$。路徑長度為 2 的路徑為 $1 \to 6 \to 6$，產生 $(1, 6)$（已存在）。
• 節點 2：
  • 直接可達：$3, 4, 5$。
  • 經由 $2 \to 3$：可至 4（$3 \to 4$）與 5（$3 \to 5$），對應 $(2, 4), (2, 5)$（皆已存在）。
  • 經由 $2 \to 4$：可至 4（自環）與 5（$4 \to 5$），對應 $(2, 4), (2, 5)$（皆已存在）。
• 節點 3：

核心觀念

本題考查關聯（Relation）與圖形理論（Graph Theory）之整合，主要涵蓋以下核心定義與定理：

1. 二元關聯的圖形表示（Graph Representation of a Relation）：
   • 設集合 $V = \{1, 2, 3, 4, 5, 6\}$ 為頂點集，關聯矩陣 $\mathbf{A} = [a_{ij}]_{6 \times 6}$ 代表有向圖 $G = (V, E)$ 的相鄰矩陣（Adjacency Matrix）。
   • 若 $a_{ij} = 1$，則存在有向邊 $(i, j) \in E$。
2. 連通性定義（Connectivity in Directed Graphs）：
   • 弱連通（Weakly Connected）：若將有向圖中所有邊的方向忽略（轉為無向圖），所得的無向圖為連通圖，則該有向圖稱為弱連通圖。
   • 強連通（Strongly Connected）：有向圖中任意兩相異頂點 $u, v$，皆存在從 $u$ 到 $v$ 以及從 $v$ 到 $u$ 的有向路徑。
3. 簡單路徑與路徑長度（Simple Path and Path Length）：
   • 路徑長度（Length of a Path）：路徑所經過的邊數（number of edges）。
   • 簡單路徑（Simple Path）：在主流計算機科學與研究所考題規範中，指**頂點不重複（no repeated vertices）**的路徑（若含 $k$ 個相異頂點，則長度為 $k-1$）。
4. 等價閉包與連通分量（Equivalence Closure & Connected Components）：
   • 關聯 $R$ 的反身、對稱且遞移閉包（Reflexive, Symmetric, and Transitive Closure）即為由 $R$ 所生成的等價關聯（Equivalence Relation）。
   • 該等價關聯的等價類（Equivalence Classes），恰好對應於 $G$ 的底層無向圖（Underlying Undirected Graph）之連通分量（Connected Components）。
5. 漢米爾頓路徑（Hamiltonian Path）：
   • 恰好經過圖中每個頂點一次的路徑。若圖不連通，則必不存在漢米爾頓路徑。

---

解題方法

由給定關聯矩陣 $\mathbf{A}$，列出有向圖 $G = (V, E)$ 的所有邊：

$$\mathbf{A} = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

• 頂點 1：邊 $(1, 6)$
• 頂點 2：邊 $(2, 3), (2, 4), (2, 5)$
• 頂點 3：邊 $(3, 4), (3, 5)$
• 頂點 4：邊 $(4, 4), (4, 5)$
• 頂點 5：無出邊（出度為 0）
• 頂點 6：邊 $(6, 6)$

觀察頂點間的有向邊分佈，圖 $G$ 可明顯劃分為兩個彼此完全無邊相連的子圖：

1. 子圖 1：頂點集合 $V_1 = \{1, 6\}$，包含邊 $(1, 6)$ 與自環 $(6, 6)$。
2. 子圖 2：頂點集合 $V_2 = \{2, 3, 4, 5\}$，包含邊 $(2,3), (2,4), (2,5), (3,4), (3,5), (4,4), (4,5)$。

$V_1$ 與 $V_2$ 之間在矩陣 $\mathbf{A}$ 中對應的所有元素皆為 $0$，兩者完全獨立。

---

核心觀念

1. 關聯矩陣（Relation Matrix）與閉包（Closures）：

   • 二元關聯 $R$ 定義在集合 $V = \{v_1, v_2, \dots, v_n\}$ 上，其關聯矩陣 $\mathbf{M}_R = [r_{ij}]$ 滿足：若 $(v_i, v_j) \in R$ 則 $r_{ij} = 1$，否則為 $0$。
   • 自反閉包（Reflexive Closure）：$r(R) = R \cup \{(x, x) \mid x \in V\}$，其矩陣為 $\mathbf{M}_{r(R)} = \mathbf{M}_R \lor \mathbf{I}_n$（主對角線元素全設為 $1$）。
   • 對稱閉包（Symmetric Closure）：$s(R) = R \cup R^{-1}$，其矩陣為 $\mathbf{M}_{s(R)} = \mathbf{M}_R \lor \mathbf{M}_R^T$。
   • 自反且對稱閉包：$S = r(s(R)) = s(r(R))$，其矩陣為 $\mathbf{M}_S = \mathbf{M}_R \lor \mathbf{M}_R^T \lor \mathbf{I}_n$。

2. 布林運算子的代數性質（Properties of Boolean Operators）：

   • 題目設定集合中的每個元素皆為命題（proposition），二元關聯 $S$ 反映布林運算子 $\circ$ 的行為，即命題 $p, q$ 滿足 $(p, q) \in S \iff (p \circ q)$ 具有特定邏輯行為。
   • 由於閉包 $S$ 必然具備：
     • 自反性（Reflexivity）：對所有命題 $p$，恆有 $(p, p) \in S$。對應布林運算必須滿足 $p \circ p \equiv \mathbf{T}$（重言／恆真）。
     • 對稱性（Symmetry）：若 $(p, q) \in S$，則 $(q, p) \in S$。對應布林運算必須具備交換律（Commutative Law），即 $p \circ q \equiv q \circ p$。

---

解題方法

第一步：求出關聯 $R$ 的自反與對稱閉包 $S$ 之矩陣 $\mathbf{M}_S$

原關係矩陣 $\mathbf{A}$ 為：

$$\mathbf{A} = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

取轉置矩陣 $\mathbf{A}^T$：

$$\mathbf{A}^T = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

將 $\mathbf{A}$、$\mathbf{A}^T$ 與單位矩陣 $\mathbf{I}_6$ 做布林聯集（Boolean OR）：

$$\mathbf{M}_S = \mathbf{A} \lor \mathbf{A}^T \lor \mathbf{I}_6 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

由矩陣結構可清楚看出：

1. 主對角線全為 $1$（具備自反性）。
2. 矩陣對稱於主對角線，即 $\mathbf{M}_S = \mathbf{M}_S^T$（具備對稱性）。
3. 元素被劃分為兩個互相獨立的完全連通子圖（等價類）：$\{1, 6\}$ 與 $\{2, 3, 4, 5\}$，因此 $S$ 同時也是一個等價關聯（Equivalence Relation）。

第二步：檢驗布林運算子的相容性

核心觀念

本題要判斷每個敘述是否符合「充分但非必要」：

• 充分：條件成立時，目標必定成立。
• 非必要：目標成立時，條件不一定成立。

因此，每個選項都要檢查兩件事：條件能否推出目標，以及目標能否在條件不成立時仍然成立。

解題方法

逐項把選項中的條件視為前提、目標視為結論。若前提不能保證結論，便不是充分條件；若目標成立必然要求前提成立，便是必要條件，因而不符合「非必要」。

選項分析

(A) 錯誤。
兩個圖同構，只能保證它們具有相同的圖形性質；但同構本身不保證它們有 Euler circuit（尤拉迴路）。例如兩個圖都可以是同構的路徑圖，而路徑圖不一定有尤拉迴路。因此「$G_1$ 和 $G_2$ 同構」不足以推出「兩者都有尤拉迴路」。

(B) 錯誤。
$g=O(f)$ 但 $g\ne\Theta(f)$，不一定能推出 $g=o(f)$。以正整數 $n$ 為例，令 $f(n)=n$，並定義

$$g(n)= \begin{cases} n, & n\text{ 為偶數},\\ 1, & n\text{ 為奇數}. \end{cases}$$

此時 $g=O(f)$，而 $g\ne\Theta(f)$，因為奇數時 $g(n)/f(n)=1/n$ 趨近於 $0$，沒有正的漸近下界；但偶數時 $g(n)/f(n)=1$，所以此比值不趨近於 $0$，即 $g\ne o(f)$。條件不充分。

核心觀念

本題為圖論（Graph Theory）與關聯（Relations）的綜合題，評量下列核心知識：

1. 路徑長度（Path Length）與頂點數：在無向圖中，長度為 $k$ 的簡單路徑（Simple Path）包含 $k$ 條邊與 $k+1$ 個頂點。若頂點總數為 $n$，則圖中能存在的最長簡單路徑之長度上限為 $n-1$。
2. 握手定理（Handshaking Theorem）：任意無向圖 $G=(V, E)$ 中，所有節點分支度（degree）的總和等於邊數的兩倍，即： $$\sum_{v \in V} \deg(v) = 2|E|$$ 此和必為偶數（Even）。
3. 連通圖（Connected Graph）的邊數下限：一個具有 $n$ 個節點的連通無向圖，其最少邊數為生成樹（Spanning Tree）的邊數，即 $|E| \ge n - 1$。因此其度數總和下限為 $2(n-1)$。
4. 鴿籠原理（Pigeonhole Principle）於分支度的應用：在包含 $n \ge 2$ 個節點的簡單圖（Simple Graph）中，必定存在至少兩個節點具有相同的分支度。
5. 關係的閉包（Closures of Relations）與連通性：若將邊視為對稱的「直接連通（directly connect）」關係 $R$，其反身傳遞閉包（Reflexive Transitive Closure）$R^*$ 即為可達性關係（Reachability Relation）。在連通圖中，任意兩節點皆互相可達，且每個節點對自身均可達，構成全域關係（Universal Relation），對應於完全圖（Complete Graph）。

---

解題方法

由題幹設定：集合 $S$ 含有 $n$ 個節點，兩節點間若 direct connect 則存在一條無向邊，形成無向簡單圖 $G$。
依據圖論的基本定義與推論，針對每個選項逐一判定其真偽。

---

選項分析

• (A) 錯誤
  簡單路徑（Simple Path）的長度定義為該路徑上所包含的邊數（number of edges）。
  若一條簡單路徑的長度為 $n$，則該路徑必須走過 $n$ 條邊，意味著必須經過 $n+1$ 個相異節點。
  然而，圖 $G$ 總共僅有 $n$ 個節點，因此圖中任意簡單路徑的長度最多只能是 $n-1$（即走遍所有 $n$ 個節點的哈密頓路徑 Hamilton path，若存在的話）。故長度為 $n$ 的簡單路徑絕對不可能存在。

• (B) 正確
  根據握手定理（Handshaking Theorem）：

  $$\sum_{i \in S} D(i) = 2|E|$$

  由於邊數 $|E|$ 為非負整數，因此 $2|E|$ 必為偶數。

• (C) 錯誤
  若圖 $G$ 為含有 $n$ 個節點的連通圖，則其邊數 $|E|$ 的最小值發生在 $G$ 為一棵樹（Tree）的情況下，此時 $|E| = n - 1$。
  由握手定理可得：

  $$\sum_{i \in S} D(i) = 2|E| \ge 2(n - 1) = 2n - 2$$

  當 $G$ 是一棵樹時，度數總和為 $2n - 2 < 2n$。

核心觀念

本題考查演算法的時間複雜度分析與遞迴關係式（Recurrence Relation）的建立。
核心包含以下三點：

1. Divide-and-Conquer 遞迴式標準形式：
   若演算法將大小為 $n$ 的問題分割為 $a$ 個子問題，每個子問題的大小為 $n/b$，其餘非遞迴工作的時間為 $f(n)$，則總時間複雜度 $F_n$ 可表示為： $$F_n = a F_{n/b} + f(n)$$
2. 非遞迴工作之成本分析：包含常數操作、迴圈執行次數與外部函式呼叫（Procedure B）的時間花費。
3. 子問題大小與遞迴呼叫次數：計算迴圈內資料被篩選進各個陣列的數量，藉此求得各子問題的規模 $m$。

---

解題方法

逐步拆解 Procedure P 每一行程式碼的執行時間與子問題規模：

1. 基本情況與外部呼叫（非遞迴部分）：

   • 第 1 行：判斷 $n < 9$，耗時 $\Theta(1)$。
   • 第 2 行：呼叫 B(array1[a1, ..., an])。已知陣列大小為 $n$，題目給定 Procedure B 的時間為 $\Theta(\sqrt{m})$，故此處耗時 $\Theta(\sqrt{n})$。宣告三個空陣列耗時 $\Theta(1)$。
   • 第 3～6 行：for (i=1 to n) 迴圈共執行 $n$ 次。迴圈內部為常數時間的條件判斷與元素插入操作，故整個迴圈的總執行時間為： $$\Theta(n)$$
   • 合併所有非遞迴部分的總花費 $f(n)$： $$f(n) = \Theta(1) + \Theta(\sqrt{n}) + \Theta(n) = \Theta(n)$$ （因為在漸近複雜度中，高階項 $\Theta(n)$ 支配低階項 $\Theta(\sqrt{n})$）。

2. 遞迴子問題的大小（Subproblem Size）：

   • 迴圈中，指標 $i$ 從 $1$ 走到 $n$：
     • 當 $i \bmod 9 = 0$ 時，將 $a_i$ 插入 array2。在 $1 \le i \le n$ 的範圍內，滿足條件的整數個數約為 $\lfloor n/9 \rfloor \approx n/9$。
     • 當 $i \bmod 9 = 3$ 時，將 $a_i$ 插入 array3，滿足條件的整數個數約為 $\lfloor (n+6)/9 \rfloor \approx n/9$。
     • 當 $i \bmod 9 = 6$ 時，將 $a_i$ 插入 array4，滿足條件的整數個數約為 $\lfloor (n+3)/9 \rfloor \approx n/9$。

核心觀念

1. 題目脈絡與遞迴演算法分析：
   本題承接第 7 題之情境（典型分治法或遞迴函式），在給定之時間複雜度遞迴式中分析子程序 $P$ 的時間複雜度階數（Order of growth）。一般分治法常見遞迴式型態為： $$T(n) = a T(n/b) + f(n)$$ 其中 $f(n)$ 即為遞迴分割或合併步驟中呼叫子程序 $P$ 所需的時間成本。
2. 大 $O$ 記號（Big-$O$ Notation）與漸近界限：
   • $f(n) = O(g(n))$ 代表 $f(n)$ 的漸近成長速率不超過 $g(n)$ 的常數倍，即存在正常數 $c, n_0$ 使得對所有 $n \ge n_0$，$0 \le f(n) \le c \cdot g(n)$。
   • 題目詢問「What <u>can be</u> the time complexity level...」，考查哪些選項在數學與演算法上構成了合法的上界，或合乎子程序 $P$ 執行成本所能落入的複雜度層級。
3. 常見函數成長速率排序： $$O(1) < O(\sqrt{n}) < O(\sqrt{n}\log n) < O(n) < O(n\log n) < O(n^{\sqrt{2}}) < O(n^{\log n})$$ 其中：
   • $n^{1/2} = \sqrt{n}$。
   • $\sqrt{2} \approx 1.414$，故 $n < n\log n < n^{\sqrt{2}} < n^2$。
   • $n^{\log n} = 2^{(\log n)^2}$ 屬於超多項式（Superpolynomial）成長等級，增長速度遠高於任意多項式。

---

解題方法

1. 第 7 題之設定推導：
   在該試卷中，第 7 題探討分治演算法（Divide-and-Conquer），由題目設計與第 7 題的遞迴模型可知，程序 $P$ 的複雜度上界為多項式或對數多項式時間。
2. 「can be」的意義判定：
   • 題幹特別將「<u>can be</u>」畫底線，表示只要該函數能夠正確作為程序 $P$ 的漸近上界（或是符合演算法成立的容許範圍），該選項即為正確。
   • 若程序 $P$ 本身的基本運算時間不超過 $O(\sqrt{n}\log n)$ 或 $O(n\log n)$，則任何漸近階數高於或等於其實際複雜度的函數，均可合法作為其 Big-$O$ 複雜度上界（例如 $O(n\log n)$ 與 $O(n^{\sqrt{2}})$）。
   • 若第 7 題原題求得 $P$ 之精確階數為 $f(n) = \Theta(\sqrt{n}\log n)$，則：
     • $O(\sqrt{n}\log n)$ 是緊密上界（Tight upper bound）。
     • 漸近階數較高者如 $O(n\log n)$ 與 $O(n^{\sqrt{2}})$ 亦構成合法之 $O(\cdot)$ 上界。
     • $O(n^{1/2}) = O(\sqrt{n})$ 因成長速率嚴格低於 $\sqrt{n}\log n$，無法涵蓋其執行時間，故不可選。

核心觀念

本題考查離散數學中**計數原理（Counting Principles）與線性遞迴關係式（Linear Recurrence Relations）**的建立：

1. 合法字串的狀態劃分：將字母集合依「是否能連續出現」進行分類，利用結尾字元的限制建立聯立遞迴關係。
2. 消去法建立二階線性遞迴關係：透過代換將聯立的一階遞迴式化簡為單一數列的二階齊次常係數線性遞迴關係式。
3. 字串長度與數列指標的對應：特別注意題目對數列下標的定義——長度為 $n$ 的合法字串數定義為 $P_{n-1}$。

---

解題方法

1. 符號定義與字母分類

字母集合大小為 $|\Sigma| = 8$，其中 $\Sigma = \{\alpha_1, \alpha_2, \ldots, \alpha_8\}$。
禁用的連續子字串為：

$$F = \{\alpha_1\alpha_1, \alpha_1\alpha_2, \alpha_2\alpha_1, \alpha_2\alpha_2\}$$

我們可將字母集合分割為兩組：

• 限制字母組 $A = \{\alpha_1, \alpha_2\}$，大小 $|A| = 2$。
• 自由字母組 $B = \{\alpha_3, \alpha_4, \ldots, \alpha_8\}$，大小 $|B| = 6$。

題意規定字串中不能出現 $F$ 中的任何子字串，這等價於：字串中不能有連續兩個來自集合 $A$ 的字母（即 $A$ 的字母後面不能緊接 $A$ 的字母）。

2. 建立遞迴關係

令長度為 $n$ 的合法字串總數為 $S_n$。我們依字串的「最後一個字元」將長度為 $n$ 的合法字串分成兩類：

• $a_n$：長度為 $n$ 且結尾字母屬於 $A$ 的合法字串數。
• $b_n$：長度為 $n$ 且結尾字母屬於 $B$ 的合法字串數。

由加法原理，顯然有：

$$S_n = a_n + b_n$$

考慮由長度 $n-1$ 延伸至長度 $n$：

1. 若第 $n$ 個字元來自 $B$（共 6 種選法）：
   前一個字元（第 $n-1$ 個）沒有任何限制，可以是任何長度為 $n-1$ 的合法字串。因此： $$b_n = 6(a_{n-1} + b_{n-1}) = 6S_{n-1}$$
2. 若第 $n$ 個字元來自 $A$（共 2 種選法）：
   第 $n-1$ 個字元絕對不能來自 $A$，因此前一個字元必須來自 $B$。即前綴必須是結尾為 $B$ 的長度 $n-1$ 合法字串。因此： $$a_n = 2b_{n-1}$$

將 $b_{n-1} = 6S_{n-2}$ 代入 $a_n$，得到：

$$a_n = 2(6S_{n-2}) = 12S_{n-2}$$

因此，長度為 $n$ 的合法字串總數 $S_n$ 之遞迴關係式為：

$$S_n = a_n + b_n = 6S_{n-1} + 12S_{n-2}, \quad n \ge 3$$

3. 轉換為題目的數列符號 $P_n$

題目定義「$P_{n-1}$ 為長度為 $n$ 的合法字串數」，即：

$$P_{n-1} = S_n \iff P_n = S_{n+1}$$

將此平移關係代入 $S_n = 6S_{n-1} + 12S_{n-2}$：

$$P_{n-1} = 6P_{n-2} + 12P_{n-3}$$

將下標整體加 1（即以 $n \ge 2$ 表示）：

$$P_n = 6P_{n-1} + 12P_{n-2}, \quad n \ge 2$$

核心觀念

本題評量**生成函數（Generating Function）在求解常係數線性遞迴關係式（Linear Recurrence Relation）**中的標準流程與技巧，核心觀念包含：

1. 生成函數與遞迴式的轉換：設數列為 $\{P_n\}_{n=0}^{\infty}$，其普通生成函數（Ordinary Generating Function）定義為 $g(z) = \sum_{n=0}^{\infty} P_n z^n$。若已知二階齊次線性遞迴關係式 $P_n - c_1 P_{n-1} - c_2 P_{n-2} = 0$（對 $n \ge 2$）及初值 $P_0, P_1$，則生成函數滿足方程式： $$g(z)(1 - c_1 z - c_2 z^2) = P_0 + (P_1 - c_1 P_0)z$$
2. 特徵方程式與分母因式分解：多項式 $1 - c_1 z - c_2 z^2$ 之根的倒數即為特徵方程式 $\lambda^2 - c_1 \lambda - c_2 = 0$ 的特徵根 $\lambda_1, \lambda_2$，可分解為 $(1 - \lambda_1 z)(1 - \lambda_2 z)$。
3. 部分分式展開法（Partial Fraction Decomposition）：利用覆蓋法（Heaviside Cover-up Method）將 $g(z)$ 拆解為： $$g(z) = \frac{A}{1 - \lambda_1 z} + \frac{B}{1 - \lambda_2 z}$$
4. 冪級數展開與通解萃取：利用幾何級數展開式 $\frac{1}{1 - \lambda z} = \sum_{n=0}^{\infty} \lambda^n z^n$，得係數 $P_n = [z^n]g(z) = A \lambda_1^n + B \lambda_2^n$。

---

解題方法

由題幹與選項結構可看出本題的遞迴系統：

• 特徵根形式為 $\lambda_{1, 2} = 3 \pm \sqrt{21}$，對應特徵多項式： $$(\lambda - (3 + \sqrt{21}))(\lambda - (3 - \sqrt{21})) = \lambda^2 - 6\lambda - 12 = 0$$
• 對應之分母為 $1 - 6z - 12z^2$。

步驟一：建立生成函數之代數關係式

將遞迴式與初始條件代入生成函數推導：

$$g(z)(1 - 6z - 12z^2) = 60z + 8$$

由此可知初始條件為：

• 常數項：$P_0 = 8$
• 一次項：$P_1 - 6P_0 = 60 \implies P_1 = 60 + 6(8) = 108$

因此，生成函數的封閉形式（Closed Form）為：

$$g(z) = \frac{8 + 60z}{1 - 6z - 12z^2}$$

步驟二：分母因式分解

方程式 $1 - 6z - 12z^2 = 0$ 的根之倒數為特徵根：

$$\lambda_1 = 3 + \sqrt{21}, \quad \lambda_2 = 3 - \sqrt{21}$$

滿足：

$$1 - 6z - 12z^2 = (1 - \lambda_1 z)(1 - \lambda_2 z) = (1 - (3 + \sqrt{21})z)(1 - (3 - \sqrt{21})z)$$

步驟三：部分分式拆解

設：

$$g(z) = \frac{A}{1 - (3 + \sqrt{21})z} + \frac{B}{1 - (3 - \sqrt{21})z}$$

使用覆蓋法（Heaviside Cover-up Method）求待定係數 $A$ 與 $B$：

• 求 $A$（令 $z = \frac{1}{\lambda_1}$）： $$A = \left. \frac{8 + 60z}{1 - \lambda_2 z} \right|_{z = 1/\lambda_1} = \frac{8 + \frac{60}{\lambda_1}}{1 - \frac{\lambda_2}{\lambda_1}} = \frac{8\lambda_1 + 60}{\lambda_1 - \lambda_2}$$ 將 $\lambda_1 = 3 + \sqrt{21}$ 與 $\lambda_1 - \lambda_2 = 2\sqrt{21}$ 代入：

核心觀念

本題評量**實對稱矩陣（Real Symmetric Matrices）**的核心代數與幾何性質，主要涉及以下定理與定義：

1. 實譜定理（Spectral Theorem for Real Symmetric Matrices）：任意 $n \times n$ 實對稱矩陣 $A$ 必可正交對角化（Orthogonally Diagonalizable），即存在正交矩陣 $Q$（$Q^T = Q^{-1}$）使得 $A = Q \Lambda Q^T$。此性質保證其具備由 $n$ 個標準正交特徵向量所構成的完備基底。
2. 代數重數與幾何重數：實對稱矩陣的每個特徵值，其幾何重數必等於代數重數。
3. 矩陣乘積的轉置性：$(AB)^T = B^T A^T$；對稱矩陣乘積 $AB$ 保持對稱的充要條件為 $AB = BA$。
4. 對稱矩陣之秩與特徵值關係：可對角化矩陣之秩等於其非零特徵值的個數（計入代數重數）。
5. 數系集合論關係：實數系為複數系的子集（$\mathbb{R} \subset \mathbb{C}$）。

---

解題方法

線性代數中討論對稱矩陣時，若無特殊聲明，預設皆在實數域 $\mathbb{R}$ 上討論（即實對稱矩陣 $A^T = A$）。解題時：

• 由譜定理判定特徵向量的正交完備性（選項 A）；
• 利用轉置運算性質檢驗加法與乘積是否滿足對稱性定義（選項 B）；
• 利用正交對角化（相似變換保秩）分析秩與零特徵值個數的關係（選項 C）；
• 依據特徵值性質及數系定義檢視命題的數學嚴謹度（選項 D）。

---

選項分析

• (A) 正確：
  根據實對稱矩陣的譜定理（Spectral Theorem），任意 $n \times n$ 實對稱矩陣 $A$ 皆可正交對角化，即存在正交矩陣 $Q$ 與對角矩陣 $\Lambda$ 使得：

  $$A = Q \Lambda Q^T$$

  其中 $Q$ 的行向量（columns）即為 $A$ 的標準正交特徵向量。即使 $A$ 具有重根（repeated eigenvalues），對應特徵值的幾何重數依然等於代數重數（即 eigenspace 的維度等於重根數）；不同特徵空間彼此互相正交，同一個特徵空間內亦可藉由 Gram-Schmidt 正交化程序取出一組標準正交基底。因此，實對稱矩陣必定擁有一組由標準正交特徵向量組成的完備基底（a complete set of orthonormal eigenvectors）。

• (B) 錯誤：
  設 $A, B$ 為對稱矩陣，即 $A^T = A$ 且 $B^T = B$。
  對於和矩陣 $A + B$：

  $$(A + B)^T = A^T + B^T = A + B$$

  故 $A + B$ 必為對稱矩陣。
  但對於乘積矩陣 $AB$：

  $$(AB)^T = B^T A^T = BA$$

  $AB$ 為對稱矩陣的充要條件是 $BA = AB$（即 $A$ 與 $B$ 可交換）。一般而言矩陣乘法不具交換律，故 $AB$ 不一定為對稱矩陣。
  反例：
  取 $A = \begin{bmatrix} 1 & 0 \\ 0 & 2 \end{bmatrix}$ 與 $B = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$，顯然皆為對稱矩陣，但：