课程名称︰离散数学
课程性质︰资讯工程学系选修
课程教师︰陈健辉
开课学院：电机资讯学院
开课系所︰资讯工程学系
考试日期（年月日）︰2015/04/10
考试时限（分钟）：150
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Examination #1
(范围:Counting Techniques)
(For each problem, please provide computation details, not the answer only)
1. Solve the following recurrence relations.
a) a_n = 5a_{n-1} + 6a_{n-2}, n >= 2, a_0 = 1, a_1 = 3. (5%)
b) a_{n+2} + a_n = 0, n >= 0, a_0 = 0, a_1 = 3. (5%)
2. The recurrence relation a_{n+2} - 10a_{n+1} + 21a_n = f(n), n >= 0,
has {a_n}^h = c_1 * 3^n + c_2 * 7^n. Give the form of {a_n}^p, if f(n)
has the following values.
(a) 5. (2%)
(b) 3n^2 - 2. (2%)
(c) 7(11^n). (2%)
(d) 2(3^n) - 8(9^n). (2%)
(e) 4(3^n) + 3(7^n). (2%)
3. Given d_3 = 2, d_4 = 9, d_5 = 44, d_6 = 265, and d_7 = 1854, how many
derangements of 1, 2, ..., 11 are there so that 1, 2, 3, 4, and 5 appear
in the first five positions. (10%)
4. In how many ways can a police captain distribute 24 rifle shells to four
police officers so that each gets at least three shells, but not more than
eight? (10%)
5. A ship carries 48 flags, 12 each of colors red, white, blue, and black.
Twelve of these flags are placed on a vertical pole in order to communicate
a signal to other ships. How many signals are there, where the total number
of blue and black flags is even? Please express your answer as 2 * a^b,
where a and b are two positive integers. (10%)
6. Professor Ruth has five graders to correct programs in her courses in Java,
C++, SQL, Perl, and VHDL. Graders Jeanne and Charles both dislike SQL,
Sandra wants to avoid C++ and VHDL. Paul detests Java and C++, and Todd
refuses to work in SQL and Perl. In how many ways can Professor Ruth assign
each grader to correct programs in one language, cover all five languages,
and keep everyone content? (10%)
7. There are (a*4^10 + b*3^9 + c*2^8 + d) 10-digit telephone numbers,
which use only the digits 1, 3, 5, and 7, with each appearing at least
twice or not at all. Please find the integers a, b, c, and d. (10%)
8. Calculate the number of ways to park at most n identical motorcycles and
at most 3 * [n/2] cars of three colors, with [n/2] cars of each color,
in a row of n (>= 1) spaces. We assume that each motorcycle requires one
space, each car needs two, and empty spaces are allowed. (10%)
9. Let a_n be the number of distinct outputs that may be generated from a
stack with n consecutive integers as inputs. Then,
a_n = a_0 * a_{n-1} + a_1 * a_{n-2} + ... + a_{n-2} * a_{1} + a_{n-1} * a_0
holds for n >= 1. Why? (10%)
10. For n >= 1, let a_n count the number of ways to write n as an ordered sum
of odd positive integers. For example, we have a_4 = 3, because
4 = 3 + 1 = 1 + 3 = 1 + 1 + 1 + 1. Show that a_n = a_{n-1} = a_{n-2}
holds for n >= 3. (10%)
11. Using a Ferrers graph, show that the number of partitions of n is equal to
the number of partitions of 2n into n summands. (10%)
12. Prove ___ ___ ___ ___
N(c_1 c_2 c_3 c_4) = N - ΣN(c_i) + ΣN(c_i c_j) - ΣN(c_i c_j c_k)
+ ΣN(c_i c_j c_k c_l)
(10 %)