109 年 國立臺灣大學工程科學及海洋工程學系碩士班丁組《離散數學（A）》

核心觀念

本題屬於計數原理中的**直線排列（Permutations）**問題。

1. 排列（Permutation）與組合（Combination）的判定：
   • 排列：從 $n$ 個不同的元素中，選出 $k$ 個元素並按照特定順序排列於 $k$ 個位置，方法數為：
     $P(n, k) = \frac{n!}{(n - k)!}$
   • 組合：若僅選出元素而不考慮排列順序，方法數為：
     $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n - k)!}$
2. 題幹條件分析：
   • 總商品種類數 $n = 256$。
   • 網頁框架總數 $k = 5 \times 5 = 25$ 個。
   • 順序性：題目提示「同商品陳列位置不同則視為不同」，代表 $5 \times 5$ 網頁框架上的每一個位置皆為獨特且不可替代的位置，因此選出的商品放置順序至關重要。
   • 干擾資訊（Distractor）：題幹提到「其中包含 100 種促銷商品」，但並未對「促銷商品」與「非促銷商品」的選取數量做任何額外限制或比例要求。因此，所有 256 種商品獲選的機會與資格完全相同，100 種促銷商品為不影響計算的干擾條件。

---

解題方法

步驟一：計算陳列位置總數

網頁上的陳列框架為 $5 \times 5$ 的網格，故共有：
$5 \times 5 = 25 \text{ 個不同位置}$

步驟二：應用乘法原理與排列公式

從 256 種不同商品中隨機選取 25 種不同商品陳列於 25 個不同框架中：

• 第 1 個框架有 256 種商品可選擇。
• 第 2 個框架剩餘 255 種商品可選擇。
• 第 3 個框架剩餘 254 種商品可選擇。
• $\dots$
• 第 25 個框架剩餘 $256 - 25 + 1 = 232$ 種商品可選擇。

根據乘法原理，總陳列方式數為：
$P(256, 25) = 256 \times 255 \times 254 \times \dots \times 232 = \frac{256!}{(256 - 25)!} = \frac{256!}{231!}$

步驟三：分步建構法驗證（先選後排）

亦可將過程拆解為兩階段：

題目缺少第 1 題所給的促銷商品數、非促銷商品數及陳列規則，無法得到唯一數值。

若共有 $P$ 種促銷商品、$N$ 種非促銷商品，選出並排列 $25$ 種不同商品，則至少 $5$ 種為促銷商品的陳列方式為

核心觀念

本題屬於組合數學（Combinatorics）中的**受限排列（Restricted Permutations）與乘法原理（Multiplication Principle）**的應用。

1. 乘法原理：若一個完成目標的程序可拆解為 $k$ 個連續且獨立的步驟，第 1 步有 $n_1$ 種方法，第 2 步有 $n_2$ 種方法，……，第 $k$ 步有 $n_k$ 種方法，則完成該目標的總方法數為：
   $N = n_1 \times n_2 \times \cdots \times n_k$
2. 相異物全排列：將 $n$ 個互不相同的元素放入 $n$ 個相異位置，其排列總數為：
   $P(n, n) = n!$
3. 受限位置優先處理：在處理含有特殊限制條件的棋盤格或陣列陳列問題時，解題策略為優先計算「受限制區域」的排列數，再計算「其餘自由區域」的排列數。

---

解題方法

本題因缺少前導題目（承上題）關於商品種類與數量設定之完整資訊，故以下採研究所離散數學試題之標準假設：設有 $25$ 件互不相同之商品填滿 $5 \times 5$ 格框架，其中包含 $5$ 件指定之相異促銷商品與 $20$ 件相異一般商品。

對於 $5 \times 5$ 的矩陣框架（共 25 個獨立位置），陳列步驟劃分如下：

1. 步驟一：第一排促銷商品的陳列
   第一排共有 5 個框架位置，需將 5 件指定的促銷商品安排於此。5 件相異促銷商品放入 5 個框架位置的全排列數為：
   $n_1 = P(5, 5) = 5! = 120$

2. 步驟二：其餘四排一般商品的陳列
   扣除第一排後，剩下的框架位置數為 $25 - 5 = 20$ 個。將剩餘 20 件相異一般商品安排於這 20 個位置的全排列數為：
   $n_2 = P(20, 20) = 20!$

核心觀念

本題考查離散機率論（Discrete Probability）中的條件機率（Conditional Probability），同時亦為資料探勘中購物籃分析（Market Basket Analysis）尋找關聯規則置信度（Confidence）的經典應用。

1. 條件機率定義：
   設 $A$ 與 $B$ 為樣本空間中的兩事件，且 $P(B) > 0$，則在已知事件 $B$ 發生的條件下，事件 $A$ 發生的條件機率定義為：
   $P(A \mid B) = \frac{P(A \cap B)}{P(B)} = \frac{N(A \cap B)}{N(B)}$
   其中 $N(B)$ 表示事件 $B$ 發生的樣本個數，$N(A \cap B)$ 表示事件 $A$ 與 $B$ 同時發生的樣本個數。

2. 問題轉化：
   題目欲求「對已經購買品5的顧客，推銷哪一種其它商品的機會最大」。在統計與機率學上，即求使條件機率 $P(\text{品}x \mid \text{品5})$ 達到最大值的商品 $x \in \{1, 2, 3, 4\}$。

---

解題方法

步驟一：分類購物記錄資料
總購物筆數 $N_{total} = 80 + 60 + 40 + 20 = 200$ 筆。各類購物記錄如下：

• $T_1 = \{ \text{品1, 品2, 品3} \}$: 80 筆
• $T_2 = \{ \text{品2, 品4} \}$: 60 筆
• $T_3 = \{ \text{品1, 品2, 品3, 品5} \}$: 40 筆
• $T_4 = \{ \text{品1, 品4, 品5} \}$: 20 筆

步驟二：計算購買「品5」的總筆數 $N(\text{品5})$
包含「品5」的購物記錄僅有 $T_3$ 與 $T_4$：
$N(\text{品5}) = N(T_3) + N(T_4) = 40 + 20 = 60 \text{ 筆}$

步驟三：分別計算各商品在「買品5」前提下的條件機率

1. 品1：
   同時包含「品1」與「品5」的記錄為 $T_3$ 與 $T_4$：
   $N(\text{品1} \cap \text{品5}) = N(T_3) + N(T_4) = 40 + 20 = 60 \text{ 筆}$
   條件機率為：
   $P(\text{品1} \mid \text{品5}) = \frac{N(\text{品1} \cap \text{品5})}{N(\text{品5})} = \frac{60}{60} = 1 \quad (100\%)$

2. 品2：
   同時包含「品2」與「品5」的記錄僅有 $T_3$：
   $N(\text{品2} \cap \text{品5}) = N(T_3) = 40 \text{ 筆}$
   條件機率為：
   $P(\text{品2} \mid \text{品5}) = \frac{N(\text{品2} \cap \text{品5})}{N(\text{品5})} = \frac{40}{60} = \frac{2}{3} \approx 0.6667 \quad (66.67\%)$

3. 品3：
   同時包含「品3」與「品5」的記錄僅有 $T_3$：
   $N(\text{品3} \cap \text{品5}) = N(T_3) = 40 \text{ 筆}$
   條件機率為：

核心觀念

在離散數學中，**集合論（Set Theory）**的子集合關係是用於衡量事件關聯性與連帶銷售（Cross-selling）強度的數學基礎。

1. 交易集合定義：
   設全集 $U$ 為所有顧客交易紀錄之集合。對於任意商品 $x$，定義 $S_x \subseteq U$ 為「購買商品 $x$ 的顧客交易集合」。
2. 商品合售之子集合關係：
   兩商品 $x$ 與 $y$ 的共同購買顧客人數對應至集合的交集（Intersection） $S_x \cap S_y$。
   若要評估將商品 $x$ 與 $y$ 一起合售促銷的機會，即衡量購買其中一商品的顧客同時購買另一商品的強度，數學上可由**單向包含度（Inclusion Degree / Confidence）與雙向重疊強度（Jaccard 相似度）**進行判斷：
   • 單向包含度（置信度）：
     $\text{Conf}(x \to y) = \frac{|S_x \cap S_y|}{|S_x|}$
     當 $S_x \subseteq S_y$ 時，$\text{Conf}(x \to y) = 1$（即 100% 購買商品 $x$ 的顧客皆購買商品 $y$），代表 $S_x$ 完全包含於 $S_y$ 中，子集合包含關係最強。
   • 雙向重疊強度（Jaccard 相似度）：
     $J(S_x, S_y) = \frac{|S_x \cap S_y|}{|S_x \cup S_y|}$
     數值越接近 $1$，代表兩商品的購買族群重疊度越高，合售促銷效果最佳。

---

解題方法

本題延續前題，缺少的條件為前題給定的各商品顧客購買交易紀錄集合；在假設前題給定商品 $A, B, C, D$ 的顧客交易集合分別為 $S_A = \{1, 2, 3, 4, 5\}$、$S_B = \{1, 2, 3, 4, 5, 6\}$、$S_C = \{1, 2, 7, 8\}$ 與 $S_D = \{9, 10\}$ 下進行推導與計算。

解題推導步驟如下：

1. 計算各商品交易集合之基數（Cardinality）：

   • $|S_A| = 5$
   • $|S_B| = 6$
   • $|S_C| = 4$
   • $|S_D| = 2$

2. 檢視商品組合之子集合與交集關係：
   針對所有可能合售的商品對 $\{x, y\}$，求出交集 $S_x \cap S_y$、聯集 $S_x \cup S_y$，並計算包含度與 Jaccard 相似度。

3. 比較包含關係與重疊度：
   找出滿足子集合包含關係（即 $S_x \subseteq S_y$）且重疊比例最高之商品對，該組合即為合售促銷機會最大者。

---

選項分析

針對各商品組合對逐一進行深入分析與比較：

• 組合 (A) 商品 $A$ 與商品 $B$：
  • 交集計算：$S_A \cap S_B = \{1, 2, 3, 4, 5\} \cap \{1, 2, 3, 4, 5, 6\} = \{1, 2, 3, 4, 5\} = S_A$。
  • 子集合關係：因為 $S_A \cap S_B = S_A$，故成立子集合關係 $S_A \subseteq S_B$。
  • 包含度與相似度：
    $\text{Conf}(A \to B) = \frac{|S_A \cap S_B|}{|S_A|} = \frac{5}{5} = 1\ (100\%)$

核心觀念

本題考驗圖論（Graph Theory）的基本定義，並結合真實巨量資料分析（購物車分析、推薦系統）進行建模應用。主要涵蓋以下觀念：

1. 購物記錄圖模型（Shopping Record Graph Modeling）：
   • 頂點集合 $V$：代表購物記錄中的各項商品。
   • 邊集合 $E$：代表商品之間的關聯性。
     • 無向邊 $\{u, v\}$：代表商品 $u$ 與商品 $v$ 經常在同一張訂單中被同時購買。
     • 有向邊 $(u, v)$：代表購買商品 $u$ 後，接著購買商品 $v$ 的順序推薦關聯。
2. 漢米爾頓迴圈（Hamilton cycle）：圖中通過所有頂點恰好一次且回到起點的閉合路徑。
3. 強連通圖（Strongly connected graph）：針對有向圖，任意兩頂點之間皆存在雙向的可達有向路徑。
4. 雙連通圖（Bi-connected graph / 重連通圖）：針對無向圖，連通且不含任何關節點（Articulation point / Cut-vertex），即移除任意單一頂點後圖形仍保持連通。

---

解題方法

解題切入點為先建立「商品關聯圖」的符號表達體系，再針對三個子題分別提供：

1. 形式化數學定義
2. 實際購物情境實務說明
3. 具體圖形範例（明確給出頂點集 $V$ 與邊集 $E$ 並驗證）

---

選項與子題分析

(a) Hamilton cycle（漢米爾頓迴圈）

• 數學定義：
  在圖形 $G = (V, E)$ 中，若存在一個閉合迴圈（Cycle）$C = (v_1, v_2, \dots, v_n, v_1)$，滿足頂點集合 $V = \{v_1, v_2, \dots, v_n\}$ 中的每一個頂點恰好出現一次，則稱此迴圈為 Hamilton cycle。
• 購物情境說明：
  在商品關聯圖中，Hamilton cycle 代表一條「全商品關聯環狀路徑」。推薦系統可以從某商品出發，依據商品間的強關聯性，不重複地遍歷商城內的所有商品，最後順暢地回到初始商品，形成完整閉環。
• 圖形舉例：
  • 設無向圖 $G = (V, E)$，頂點代表商品：
    $V = \{A, B, C, D\} \quad (A:\text{麵包}, B:\text{奶油}, C:\text{牛奶}, D:\text{咖啡})$
  • 關聯邊集：
    $E = \{\{A, B\}, \{B, C\}, \{C, D\}, \{D, A\}\}$
  • 驗證：路徑 $A \to B \to C \to D \to A$ 經過了所有頂點集合 $V$ 中的元素恰好一次，最終回到起點 $A$，故此圖包含一個 Hamilton cycle。

(b) Strongly connected graph（強連通圖）

• 數學定義：
  設 $G = (V, E)$ 為一個有向圖（Directed Graph）。若對於圖中任意兩相異頂點 $u, v \in V$，都存在一條從 $u$ 到 $v$ 的有向路徑（Directed path），且亦存在一條從 $v$ 到 $u$ 的有向路徑，則稱 $G$ 為 Strongly connected graph。
• 購物情境說明：
  在商品順序購買導引圖中，有向邊 $(u, v)$ 代表「購買 $u$ 後會被引導購買 $v$」。若此圖為強連通圖，代表從任意商品出發，都能透過一系列的推薦鏈到達系統內的任何其他商品，不存在無法抵達的「死角商品」。
• 圖形舉例：
  • 設有向圖 $G = (V, E)$，頂點代表商品：
    $V = \{A, B, C\} \quad (A:\text{手機}, B:\text{保護貼}, C:\text{手機殼})$
  • 購買引導邊集：

核心觀念

1. 整數封閉性與奇偶性約束（Parity Constraint）：
   在不定方程 $x + y + \frac{z}{2} = 100$ 中，由於 $x, y$ 均為整數且右式 $100$ 亦為整數，故分數項 $\frac{z}{2} = 100 - x - y$ 必須為整數。這意味著 $z$ 必然為偶整數。
2. 重複組合（Combination with Repetition / Multiset Coefficient）：
   若求 $n$ 個變數之和等於常數 $m$ 的非負整數解個數（即 $x_1 + x_2 + \cdots + x_n = m$，且 $x_i \ge 0$），公式為：
   $H_m^n = H(n, m) = \binom{n+m-1}{m} = \binom{n+m-1}{n-1}$

---

解題方法

步驟一：確立變數的精確範圍與約束

• $x > 12$ 且 $x \in \mathbb{Z} \implies x \ge 13$。
• $12 > y > 8$ 且 $y \in \mathbb{Z} \implies y \in \{9, 10, 11\}$。
• $z > 8$ 且 $z$ 為偶整數 $\implies z \in \{10, 12, 14, \dots\}$。

步驟二：變數代換簡化方程
設 $z = 2k$，其中 $k$ 為整數。
由 $z \ge 10$ 可得 $2k \ge 10 \implies k \ge 5$。
將 $z = 2k$ 代入原方程 $x + y + \frac{z}{2} = 100$，簡化為：
$x + y + k = 100$

步驟三：轉換為非負整數變數
定義平移變數：

• $x' = x - 13 \ge 0 \implies x = x' + 13$
• $k' = k - 5 \ge 0 \implies k = k' + 5$

將 $x, k$ 代入方程：
$(x' + 13) + y + (k' + 5) = 100$
$x' + k' = 82 - y$
其中 $x', k'$ 均為非負整數。

步驟四：依 $y$ 之可能取值進行分類討論

1. 當 $y = 9$ 時：
   $x' + k' = 82 - 9 = 73$

核心觀念

1. 冪集合（Power Set）定義
   對任意集合 $S$，由 $S$ 之所有子集（Subsets）所組成的集合稱為 $S$ 的冪集合，記作 $\mathcal{P}(S)$ 或 $2^S$：
   $\mathcal{P}(S) = \{ A \mid A \subseteq S \}$

2. 集合勢（Cardinality）與二項式定理
   若原集合 $S$ 含有 $n$ 個互異元素（即 $|S| = n$），則其冪集合的元素個數（即子集總數）為：
   $|\mathcal{P}(S)| = 2^n$
   此性質源於二項式定理：從 $n$ 個元素中分別選取 $0, 1, 2, \dots, n$ 個元素的組合數總和為 $\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$。

3. 位元映射（Bitmask Mapping）與雙射（Bijection）
   大小為 $n$ 的集合中，每個元素在子集中僅有「選取（$1$）」或「不選取（$0$）」兩種決策。因此，每個子集皆可一對一映射至一個長度為 $n$ 的二進位數。整數範圍介於 $0$ 至 $2^n - 1$ 之間的 $2^n$ 個二進位狀態，與 $\mathcal{P}(S)$ 中的每一個子集形成雙射關係。

---

解題方法

本題要求編寫程式輸入字元集合字串並輸出其冪集合。最優且最精簡的實作策略為位元遮罩法（Bitmask Approach）。

演算法邏輯與推導步驟

1. 去重與初始化：集合內的元素具備「互異性」，輸入字串若包含重複字元應先進行去重處理解析出基底集合 $S$，設其長度為 $n$。
2. 生成二進位狀態：利用迴圈讓整數變數 $i$ 從 $0$ 遞增至 $2^n - 1$（即 (1 << n) - 1）。
3. 檢查位元與輸出：對於每個狀態 $i$，遍歷其第 $j$ 個位元（$0 \le j < n$）：
   • 若位元運算 (i >> j) & 1 為 $1$，代表子集包含第 $j$ 個字元 $S[j]$。
   • 若為 $0$，則代表不包含。
4. 構造對應子集：印出該狀態所代表的子集內容，即可不重不漏地輸出完整冪集合。

完整程式碼實作（以 C++ 寫作）