107 中山資工所考古題解答｜數學考點分析

全卷 1 頁 6 題，全部申論，卷首規定沒有詳細步驟該題不給分。有 generating function 的係數、onto 函數的 exponential generating function、A∗ 的字串計數與遞迴，第 4 到 6 題共 40 分是 group theory。

題型與配分

全卷 1 頁、6 題、100 分，不可使用計算機。卷首規定每題都要寫出詳細步驟，否則該題不給分。

題號	主題	配分
1	generating function 中 x⁷ 的係數	20%（10+10）
2	onto 函數個數的 exponential generating function	20%（10+10）
3	A = {1, 00, 10} 的 A∗ 字串計數	20%（10+10）
4	additive group (Z₈, +)	10%（5+5）
5	multiplicative group (Z∗₁₉₆, ·)	10%（5+5）
6	Z×Z 上自訂運算 ⊕ 的 group 與 homomorphism	20%（2+5+5+8）

第 1 題（20%）｜求下列各式中 x⁷ 的係數：(a) 10% ((x² − 3x)/(1 − x)⁵) + 3x⁷ + 5 (b) 10% −2/((x − 1)(x − 2))
第 2 題（20%）｜計算 onto 函數 H: A → B 的個數，其中 |A| ≥ |B|：(a) 10% 求一個 exponential generating function，使 x^|A|+2/|A|! 的係數就是這個個數 (b) 10% 用這個 exponential generating function 求 |A| = 10、|B| = 3 時的個數
第 3 題（20%）｜字母表 Σ = {0, 1}，A = {1, 00, 10} 是 Σ∗ 的子集：(a) 10% a_n 為 A∗ 中長度 n 的字串個數（n ≥ 1），求並解 a_n 的 recurrence relation (b) 10% b_n 為 A∗ 中長度 n、把字串當成二進位數時能被 2 整除的字串個數（卷面寫 exactly divided by 2），求 b_n
第 4 題（10%）｜additive group (Z₈, +)：(a) 5% 6 的階（order）是多少，為什麼 (b) 5% 找出這個 group 所有的 generator
第 5 題（10%）｜multiplicative group (Z∗₁₉₆, ·)：(a) 5% 這個 group 的 order 是多少，為什麼 (b) 5% 求 25 的 inverse
第 6 題（20%）｜(Z×Z, ⊕) 是 group，(a,b) ⊕ (c,d) = (a+c+2, b+d−2)，加減用 Z 上的一般運算：(a) 2% 3(4,5) = (4,5) ⊕ (4,5) ⊕ (4,5) (b) 5% 這個 group 的 identity element (c) 5% (a,b) 的 inverse (d) 8% (G, +) 是 additive group，h: Z×Z → G 是 group homomorphism，h(3,2) = u、h(−2,6) = v，用 u 與 v 表示 h(18,22)

generating function 的係數（107 第 1 題），106 第 2 題、108 第 7 題、109 第 6 題、112 第 5 題、113 第 10 題也有 generating function。
exponential generating function 與 onto 函數計數（107 第 2 題），109 第 3 題、114 第 3 題、115 A8 也有函數個數。
Σ∗ 的子集與字串計數（107 第 3 題），108 第 6 題也考 Σ∗ 的子集合，110 第 4 題、112 第 4 題、115 A9 是字串計數。
recurrence relation（107 第 3 題），106 第 2 題、109 到 114 年也有。
group theory 與同態（107 第 4、5、6 題），106 到 115 年只有這一年考 group；109 第 3 題、113 第 6 題考的是 binary operation 的 closure、commutativity 與 associativity。
modular inverse（107 第 5(b) 題），110 第 7 題、113 第 4 題也有。