課程名稱︰離散數學
課程性質︰資訊工程學系選修
課程教師︰陳健輝
開課學院：電機資訊學院
開課系所︰資訊工程學系
考試日期（年月日）︰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 %)