一、單選題

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.

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.

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.

二、計算題

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.$

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.

9 留言

1. K

你好，請問計算第一題的遞迴式是怎麼推得的?

• 文章作者的留言

mt

這題的話我們可以先假設$b_n$為containing an even number of 1’s的字串，就可以得到：
$a_n = 4a_{n-1} + b_{n-1}$
又因為$a_n + b_n = 5^n$
可以得到$a_n = 3a_{n-1} + 5^{n-1}$。

• K

了解!感謝用心答覆

2. Nelson

你好，關於計算題第2題，我自己算是算168。
然後我用電腦爆搜6!後的結果也是168。跟答案剛好差了2倍

• 文章作者的留言

mt

算出168會不會是你沒有除以2，因為有兩個一樣的P，像是這樣：
A$P_1$LO$P_2$T
A$P_2$LO$P_1$T
就會被算兩次～

3. jim

可以請問一下計算題第2題解法嗎?
自己用了城堡多項式弄了好久還是兜不出來..

• 文章作者的留言

mt

這題可以用排容原理喔！
假設第一個P為$P_1$第二個P為$P_2$，則在$D_6$中$P_1$不會出現在第三個位置，$P_2$不會出現在第六個位置。
所以我們只要再排除$P_1$在第六個位置及$P_2$在第三個位置的情況就好了！
設$c_1$表示$P_1$在第六個位置的情況，$c_2$表示$P_2$在第三個位置的情況，則$N(\overline{c_1} \overline{c_2})=N-N(c_1)-N(c_2)+N(c_1c_2)=D_6-2(D_4+D_5)+D_4$
最後再除以$2!$就是答案囉！

• 242ca

請問為什麼N(c1) = (D4 + D5)

• 文章作者的留言

mt

因為算$N(c_1)$的時候要考慮$P_2$是不是被放在第三個位置，如果$P_2$在第三個位置那就是$D_4$，不然就是$D_5$。