课程名称︰离散数学
课程性质︰资讯工程学系选修
课程教师︰陈健辉
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰2014/03/28
考试时限（分钟）：160
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Examination #1
(范围:Combinatorics)
(For each problem (except problems 5, 10 and 12), please provide computation
details, not the answers only.)
1. There are five books undergoing a two-round review process of five
reviewers. Each book is reviewed by two distinct reviewers. In how many ways
can these books be reviewed? (10%)
2. How many one-to-one funcitons f:{1,, 2, 3, 4}→{u, v, w, x, y, z} are there
so that f(1)\notin {u, v}, f(2)\notin {v, w}, f(3)\notin {x, y}, and f(4)
\notin {x, y, z}? (10%)
3. Determine how many integer solutions there are to x_1 + x_2 + x_3 + x_4 = 19
if 0≦x_1≦5, 0≦x_2≦6, 3≦x_3≦7, 3≦x_4≦8. (10%)
4. Determine how many 4-element subsets of S={1, 2, ..., 12} contain no
consecutive integers. (10%)
5. Explain why the number of partitions of 14 into 6 summands is identical with
the number of partitions of 14 whose maximal summand is 6. (10%)
6. There are 4^20 quaternary (0, 1, 2, 3) sequences of length 20, and a*3^20 +
b*3^18 of them each have exactly two 3's or none at all. Write (a, b). (10%)
7. Find the general solution for the recurrence relation a_{n+3} - 3a_{n+2} -
a_n = 3 + 5n, where n≧0. (10%)
8. For n≧0, let a_n count the number of ways a sequence of 1's and 2's will
sum to n. For example, a_3 = 3 because (1, 1, 1), (1, 2) and (2, 1) sum to 3
Find and solve a recurrence relation for a_n. (10%)
9. If you want to take out a loan of 10000 dollars with interest rate 2% per
year and pay it back in 20 years, then you must make a constant payment
P = α* (β- γ^-20)^-1 at the end of each year. Write (α, β, γ). (10%)
10.Let a_n be the number of distinct outputs that may be generated from a stack
with n consecutive integers as inputs. Find a recurrence relation for a_n
and explain your answer. (10%)
11.Let f(x) be the ordinary generating function of (a_0, a_1, a_2, ..., a_n, ..
.), where a_0 = 1 and a_n = 2a_{n-1} + 3 for n ≧ 1. Find b_n so that
(1-x)f(x) is the generating function of (b_0, b_1, b_2, ..., b_n, ...).
(hint: if h(x) is the ordinary generating function of (c_0, c_1, c_2, ...,
c_n, ...), then h(x)/(1-x) is the ordinary generating function of (c_0, c_0+
c_1, c_0+c_1+c_2, ...)). (10%)
12.An arrangement of 1, 2, ..., n is called a derangement, if each number is
not at its natural position, i.e., 1 is not at the first place, 2 is not at
the second place, ..., and n is not at the nth place. Let d_n be the number
of derangements of 1, 2, ..., n. Clearly, we have d_1 = 0 and d_2 = 1. Show
that when n>2, we have d_n = (n-1)(d_{n-1} + d_{n-2}). (hint: first consider
the location of 1, say the ith place (i≠1), and then consider the location
of i.) (10%)