Processing math: 79%

考試

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

1. For n1, let an count the number of ways to write n as an ordered sum of odd positive integers. (For example, a4=3 since 4 = 3+1 = 1+3 = 1+1+1+1.) Find and solve a recurrence relation for an. (15%)

參考解答:an=an1+an2,n3. a1=1,a2=1.


2.

(a) How many bit strings of length 8 do not contain three consecutive 1s? (10%)
(b) What is the probability that a ternary sequences (sequence made up of the digits 0, 1, 2) of length 8 contains even number of 1’s bits? (10%)

參考解答:
(a) 149
(b) 328138


3. Let p,q be two distinct primes. We denote relation xRy if x divides y. Under this relation R, please determine (a) the Hasse diagram of all positive divisors of p2q2, (b) glb{pq,p2}, (c) How many edges are there in the Hasse diagram of all positive divisors of pmq2,mZ+. (15%)

參考解答:
(a)

mt01

(b) p
(c) 5m+2


試題(pdf):連結

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

2 留言

  1. michael

    您好,想要請問一下第6題的recurrence relation是如何得到的呢?

    我自己的想法是: 要湊成整數n,一定會有一個最後一個被選到的奇數,如果最後一個選到的是1,那方法數相當於an1, 如果是3,那方法數相當於a_{n – 3},以此類推可以得到:
    a_n = a_{n – 1} + a_{n – 3} + a_{n – 5} + ….
    而後面a_{n-3} + a_{n-5} + … 的總合又相當於a_{n-2}
    因此可以得到a_{n} = a_{n – 1} + a_{n-2}

    不知道您是這樣得到的還是用其他觀點切入呢,謝謝。

發佈留言