考試

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):連結

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

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}$。

  2. Nelson

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

  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!$就是答案囉!

發佈留言