100成大資工離散[參考解答]

一、單選題

1. (5%) The probability of each summand is a multiple of 3 in all compositions of 18 is

(A) $1/3^{11}.$
(B) $1/3^{12}.$
(C) $1/2^{11}.$
(D) $1/2^{12}.$
(E) None of the above.

參考解答：D

---

2. (5%) Which statement is NOT correct?

(A) The coefficient of $x^5$ in $(1 – 2x)^{-7}$ is $(32) \binom{11}{5}.$
(B) $\sum_{k=0}^{20} (-1)^k \binom{20}{20-k} (20 – k)^{15} = 0$
(C) If $|A| = |B| = 6,$ there are $6!$ functions $f:A \rightarrow B$ are invertible.
(D) The sequence generated by $f(x) = \dfrac{1}{3-x}$ is $(- \dfrac{1}{3}), \, (- \dfrac{1}{3})^2, \, (- \dfrac{1}{3})^3, \, (- \dfrac{1}{3})^4, …$
(E) None of the above.

參考解答：D

---

3. (10%) Suppose $S(n)$ is a predicate on natural numbers, $n,$ and suppose $\forall k \in \mathbb{N}, S(k) \rightarrow S(k+2)$ hold. Which one following statements NEVER hold?

(A) $\forall n \geq 0 \, S(n).$
(B) $\forall n \geq 0 \, \neg S(n).$
(C) $[\exists n \, S(2n)] \rightarrow \forall n \, S(2n+2).$
(D) $(\forall n \leq 100 \, \neg S(n)) \wedge (\forall n > 100 \, S(n)).$
(E) None of the above.

參考解答：E

---

二、計算題

1. (15%) Let $\sum = \{0, \, 1, \, 2, \, 3, \, 4\}.$ For $n \geq 1,$ let $a_n$ count the number of string in $\sum^n$ containing an odd number of 1’s. Find and solve a recurrence relation for $a_n.$

參考解答：$a_n = 3a_{n-1} + 5^{n-1} = \dfrac{1}{2} (5^n – 3^n)$

---

2. (15%) Find the number of ways to arrange the letters in LAPTOP so that none of the letters L, A, T, O is in its original position and the letter P is not in the third or sixth position.

參考解答：84

---

試題(pdf)：連結

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