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

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) $\dfrac{3281}{3^8}$

3. Let $p, \, q$ be two distinct primes. We denote relation $x R y$ if $x$ divides $y.$ Under this relation $R,$ please determine (a) the Hasse diagram of all positive divisors of $p^2q^2,$ (b) $glb\{pq, \, p^2\},$ (c) How many edges are there in the Hasse diagram of all positive divisors of $p^mq^2, \, m \in Z^+.$ (15%)

(a)

(b) $p$
(c) $5m + 2$

### 2 留言

1. #### michael

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

我自己的想法是: 要湊成整數n，一定會有一個最後一個被選到的奇數，如果最後一個選到的是1，那方法數相當於$a_{n-1}$， 如果是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}$

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