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

核心觀念

本題旨在考驗離散數學中組合數學的核心主題：多項式定理（Multinomial Theorem）。

多項式定理為二項式定理的推廣，用以求取多項和（Multinomial）次方的展開式中各項之係數。其定理定義如下：

設 $n$ 為正整數，對任意實數 $x_1, x_2, \dots, x_m$，展開式 $(x_1 + x_2 + \dots + x_m)^n$ 的一般項為：
$\binom{n}{k_1, k_2, \dots, k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m} = \frac{n!}{k_1! k_2! \cdots k_m!} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$
其中各次數指數必須滿足約束條件：
$k_1 + k_2 + \dots + k_m = n \quad \text{且} \quad k_i \ge 0 \; (i = 1, 2, \dots, m)$

解題方法

步驟一：對照多項式定理形式
將給定多項式 $(3a - b + 5c + 3d - 8)^{25}$ 對應至 $m = 5$ 項和的 25 次方形式：
$(x_1 + x_2 + x_3 + x_4 + x_5)^{25}$
其中各項分別設定為：

• $x_1 = 3a$
• $x_2 = -b$
• $x_3 = 5c$
• $x_4 = 3d$
• $x_5 = -8$

步驟二：寫出一般項公式
根據多項式定理，展開式中的一般項可表示為：
$\binom{25}{k_1, k_2, k_3, k_4, k_5} (3a)^{k_1} (-b)^{k_2} (5c)^{k_3} (3d)^{k_4} (-8)^{k_5}$
將數值係數與變數分離後可得：
$\frac{25!}{k_1! k_2! k_3! k_4! k_5!} \cdot 3^{k_1} \cdot (-1)^{k_2} \cdot 5^{k_3} \cdot 3^{k_4} \cdot (-8)^{k_5} \cdot a^{k_1} b^{k_2} c^{k_3} d^{k_4}$

步驟三：決定各指數 $k_i$ 的值
目標為求取 $ab^6c^8d^5 = a^1 b^6 c^8 d^5$ 的係數，比對變數 $a, b, c, d$ 的次數：

• $k_1 = 1$ （對應 $a^1$）
• $k_2 = 6$ （對應 $b^6$）
• $k_3 = 8$ （對應 $c^8$）
• $k_4 = 5$ （對應 $d^5$）

利用指數總和等於總次方數 $n = 25$ 的約束條件 $k_1 + k_2 + k_3 + k_4 + k_5 = 25$：
$1 + 6 + 8 + 5 + k_5 = 25 \implies 20 + k_5 = 25 \implies k_5 = 5$

核心觀念

1. 互質（Co-prime / Relatively Prime）定義
   對任意兩整數 $a, b \in \mathbb{Z}$，若其最大公因數為 $1$，即 $\gcd(a, b) = 1$，則稱 $a$ 與 $b$ 互質。
2. 最大公因數的線性組合性質（Bézout's Identity 定理延伸）
   若 $d = \gcd(a, b)$，則對任意整數 $x, y \in \mathbb{Z}$，公因數 $d$ 必能整除 $a$ 與 $b$ 的任意整數線性組合，即 $d \mid (ax + by)$。特別地，若能找到整數 $x, y$ 使得 $ax + by = 1$，因為最大公因數依定義必為正整數（$d \ge 1$），故可直接判定 $\gcd(a, b) = 1$。
3. 輾轉相除法（Euclidean Algorithm）
   對任意整數 $a, b, q, r$，若 $a = bq + r$，則 $\gcd(a, b) = \gcd(b, r)$。

解題方法

本題為數論中的標準證明題，可採用線性組合法（消元法）或輾轉相除法進行推導。

方法一：線性組合法（推薦解法）

設 $d = \gcd(12n+17, 8n+11)$，其中 $n \in \mathbb{Z}^{+}$。

依據最大公因數的定義，$d$ 同時為 $12n+17$ 與 $8n+11$ 的因數：
$d \mid (12n+17) \quad \text{且} \quad d \mid (8n+11)$

根據整除的線性組合性質，$d$ 必整除兩式的任意整數組合。為了消去含 $n$ 的項，觀察 $12$ 與 $8$ 的最小公倍數為 $24$，選取係數 $2$ 與 $-3$：
$d \mid \left[ 2 \cdot (12n+17) - 3 \cdot (8n+11) \right]$

將括號內部展開並化簡：
$2 \cdot (12n+17) - 3 \cdot (8n+11) = (24n + 34) - (24n + 33) = 1$

由此可得：
$d \mid 1$

因為最大公因數依定義恆為正整數（$d \in \mathbb{Z}^{+}$），而正整數中能整除 $1$ 的數僅有 $1$，故 $d = 1$。

即 $\gcd(12n+17, 8n+11) = 1$，證畢。

方法二：輾轉相除法

將倉庫依物流路線排序，考慮其容量序列。由 Erdős–Szekeres 單調子序列定理，任意 $25=5^2$ 個互異數值中，必存在長度至少 $5$ 的遞增或遞減子序列。

「$xyz$ 為真前綴」表示字串以 $xyz$ 開頭，且其後至少還有一個字元。因此符合條件的字串集合為

三序列的摺積為

代入 $a_i=(-1)^i$、$b_j=(-1)^j$、$c_k=1$，令 $m=i+j$；固定 $m$ 時共有 $m+1$ 組 $(i,j)$，故

每面旗只需區分顏色，故訊號可視為長度 $15$ 的四色序列；各色最多使用 $15$ 面的限制不影響計數。

(a) 以奇偶篩選法計數。令黑旗數為 $b$、紅旗數為 $r$，則所求為

對所有四色序列加總：

(b) 設

• $A$：至少有 $5$ 面白旗；
• $B$：沒有藍旗。

利用排容原理：

核心觀念

1. 相異物排列與無庫存限制性：
   題目給定紅（R）、白（W）、藍（B）、黑（K）四種顏色的旗子各 15 面，總共 60 面旗子。要在垂直旗桿上擺放 15 面旗子進行排列。由於總長度僅為 15，任何一種顏色即使 15 面全選也不會超過庫存上限。因此，每一個位置選擇 4 種顏色皆可獨立進行，不受庫存數量的限制。在無任何條件限制下，總訊號數為 $4^{15}$ 種。
2. 指數型生成函數 (Exponential Generating Function, EGF)：
   在考慮相異位置排列且對元素出現次數的「奇偶性」有要求時，EGF 是最經典且標準的解題工具：
   • 任意次數：$e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$
   • 偶數次數：$\cosh(x) = \frac{e^x + e^{-x}}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots$
   • 奇數次數：$\sinh(x) = \frac{e^x - e^{-x}}{2} = x + \frac{x^3}{3!} + \frac{x^5}{5!} + \cdots$
3. 取捨原理 (Principle of Inclusion-Exclusion, PIE) 與補集計數：
   處理包含聯集條件（如「條件 $A$ 或條件 $B$」）的計數問題時，可透過 $|A \cup B| = |A| + |B| - |A \cap B|$ 或利用對立事件之補集法 $|A \cup B| = |S| - |A^c \cap B^c|$ 來化簡計算。

解題方法

(a) 使用奇數面黑旗與偶數面紅旗之訊號數

步驟一：建立指數型生成函數 (EGF)
設長度為 $n$ 的訊號中，黑旗數量為奇數、紅旗數量為偶數、白旗與藍旗數量不限。各顏色的生成函數分別為：

• 黑旗（奇數面）：$\frac{e^x - e^{-x}}{2}$
• 紅旗（偶數面）：$\frac{e^x + e^{-x}}{2}$
• 白旗（無限制）：$e^x$
• 藍旗（無限制）：$e^x$

整體排列的生成函數 $f(x)$ 為：
$f(x) = \left( \frac{e^x - e^{-x}}{2} \right) \cdot \left( \frac{e^x + e^{-x}}{2} \right) \cdot e^x \cdot e^x$

步驟二：化簡生成函數並求特定項係數
利用平方差公式與指數律進行簡化：
$f(x) = \left( \frac{e^{2x} - e^{-2x}}{4} \right) \cdot e^{2x} = \frac{e^{4x} - 1}{4} = \frac{1}{4}e^{4x} - \frac{1}{4}$

將 $e^{4x}$ 展開為麥克勞林級數（Maclaurin Series）：
$e^{4x} = \sum_{n=0}^{\infty} \frac{(4x)^n}{n!} = \sum_{n=0}^{\infty} 4^n \cdot \frac{x^n}{n!}$

步驟三：計算長度為 15 之訊號數
所求即為 $f(x)$ 中 $\frac{x^{15}}{15!}$ 的係數：
$\text{訊號數} = \frac{1}{4} \cdot 4^{15} = 4^{14}$
（數值解為 $2^{28} = 268,435,456$）

(b) 至少有五面包旗或完全沒有藍旗之訊號數

步驟一：定義事件與問題轉化
設全集 $S$ 為長度 15 的所有可能訊號，$|S| = 4^{15}$。

• 事件 $A$：白旗至少五面（$w \ge 5$）
• 事件 $B$：完全沒有藍旗（$b = 0$）

所求為 $|A \cup B|$。採用補集計數法計算對立事件 $(A \cup B)^c = A^c \cap B^c$，即「白旗少於五面（$w \in \{0, 1, 2, 3, 4\}$）且藍旗至少一面（$b \ge 1$）」。

核心觀念

將每個停車位置視為一段連續空間：

• 機車占用 $1$ 格。
• 汽車占用連續 $3$ 格。
• 停車方式的差異在於車輛種類排列的位置不同。
• 以「最後一輛車」作分類，可建立遞迴關係。

令 $a_n$ 表示長度為 $n$ 的停車格排列方式數。

(a) 機車占 1 格、汽車占 3 格

解題方法

考慮最右側停放的車輛：

1. 若最右側是機車，前面剩下 $n-1$ 格，有 $a_{n-1}$ 種排法。
2. 若最右側是汽車，汽車占用最後 $3$ 格，前面剩下 $n-3$ 格，有 $a_{n-3}$ 種排法。

兩種情況互斥且涵蓋所有可能，因此：

初始條件為：

• $a_0=1$：沒有停車格時，空排列算 $1$ 種。
• $a_1=1$：只能停一台機車。
• $a_2=1$：只能停兩台機車。

所以：

前幾項

因此數列為：

特徵方程解法

假設解為 $a_n=r^n$，代入遞迴式：

除以 $r^{n-3}$ 得：

設此方程式的三個根為 $r_1,r_2,r_3$，則一般解為：

利用初始條件可寫成：

其中 $r_i$ 是方程式 $r^3-r^2-1=0$ 的三個根。

也可用生成函數表示。令

由遞迴關係可得：

因此：

(b) 汽車有四種顏色

令 $b_n$ 表示長度為 $n$ 的停車格排列方式數。

解題方法

同樣依最右側車輛分類：

1. 最右側是機車：有 $b_{n-1}$ 種排法。
2. 最右側是汽車：汽車占 $3$ 格，且有 $4$ 種顏色，因此有 $4b_{n-3}$ 種排法。

所以遞迴關係為：

初始條件仍為：

前幾項

由 $a\equiv b\pmod n$，可知存在 $k\in\mathbb Z$，使得

$a=b+kn.$