104成大資聯離散[參考解答]

1. Let $\Sigma = \{0, \, 1\}$ and $A = \{0, \, 01, \, 11\} \subseteq \Sigma^*.$ For $n \geq 1,$ let $a_n$ count the number of strings in $A^*$ of length $n.$ Find and solve a recurrence relation for $a_n.$ (10%)

參考解答：$a_n = a_{n-1} + 2a_{n-2}, \, \forall n \geq 3. \, a_1 = 1, \, a_2 = 3. \\ \to a_n = \dfrac{2}{3} \cdot 2^n + \dfrac{1}{3} \cdot (-1)^n$

---

2. Let $A = \{a, \, b, \, c, \, d, \, e\},$

(a) How many closed binary operations $f$ on $A$ satisfy $f(a, \, b) \neq c?$
(b) How many closed binary operations $f$ on $A$ have an identity and $f(a, \, b) = c?$
(c) How many $f$ in (b) are commutative?
(d) Determine the number of relations on $A$ that are reflexive and symmetric but not transitive.
(e) Determine the number of equivalence relations where $b \in [e].$
(Note: Values of Stirling number of the second kind: S(4,2)=7, S(4,3)=6, S(5,2)=15, S(5,3)=25) (20%)

參考解答：(a) $4 \times 5^{24}$ (b) $3 \times 5^{15}$ (c) $3 \times 5^9$ (d) 972 (e) 15

---

3. (a) Find the number of permutations of 0, 1, 2, 3, …, 8 in which none of the patterns ‘1234’, ’76’, ’23’, ’81’ occurs. (b) How many three-element subsets of $S = \{1, \, 2,…, \, 10\}$ contains no consecutive integers? (20%)

參考解答：
(a) $9! – (3 \times 8!) + (3 \times 7!) – 6! = 256320$
(b) $\binom{4+5-1}{5} = \binom{8}{5} = 56$

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！