课程名称︰离散数学 课程性质︰资讯系选修 课程教师︰陈健辉 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰2012/4/2 考试时限（分钟）：120 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Examination #1 (范围：Combinatorics) (For each problem, please provide computation details, not only the answer.) 1.Two cases of soft drinks, 21 bottles of one type and 21 of another, are distributed among four surveyors who are conducting taste tests. In how many ways can the 42 bottles be distributed so that each surveyor gets at least two bottles of each type? (10%) 2.A ship carries 40 flags, 10 each of red, white, blue and black. Eight of these flags are placed on a vertical pole in order to communicate a signal to other ships. How many of these signals use an even number of blue and an odd number of black flags? (10%) 3.Let a_n te the number of ordered rooted binary trees on n vertices. (1) Find a recurrence relation for a_n. (5%) (2) Is the recurrence relation of (1) linear of non-linear? Why? (3%) (3) Is the recurrence relation of (1) homogeneous or non-homogeneous? Why? (2%) 4.Jeremy Lin decides to purchase an apartment in New York, and so he considers taking out a loan of $300,000. If the loan is to be paid back with 20 years and the interest rate per year is 2%, then what payment must he make at the end of each year? Please round off the yearly payment to the nearest whole number(四舍五入取整数值), using the approximation of (1 + 0.02)^{-20}≒0.673 (10%) 5.The homogeneous solution (i.e., {a_n}^h) to a_n + 4a_{n-1} + 4a_{n-2} = f(n), n≧2, is c_1(-2)^n + c_2n(-2)^n. What are the forms of particular solutions (i.e. {a_n}^p) for the following f(n): (1) 7; (2) n^2+1; (3) 9(-2)^n; (4) 6n(-2)^n; (5) n^2(-2)^n ? (2% each) (For this problem, you are required to provide the answers only, not the details.) 6.Solve a_n - 2a_{n-1} = 4^{n-1}, n≧1, a_0 = 1, by the method of generating function. (10%) 7.At an 11-week conference in mathematics, Sharon met six of her friends from college. During the conference she met each friend at lunch 30 times, every pair of them 14 times, every trio eight times, every foursome four times, each set of five once, but never all six at once. If she had lunch every day during the 77 days of the conference, how many days she had lunch alone? (10%) 8.Explain why the number of partitions of n into m summands is equal to the number of partitions of n into summands with m being the largest summand. (10%) 9.Consider the Hanoi tower problem. Let A_n be the minimal number of disk moves required to transfer n disks from peg 1 to peg 3. Explain why a_n = 2a_{n-1} + 1. (10%) A.Please provide a combinatorial proof, not an inductive proof, for the principle of inclusion and exclusion, i.e. the number of elements in a set that satisfy none of conditions c_1, c_2, ..., c_t is equal to ___ ___ ___ N(c_1 c_2 ... c_t) = N - ΣN(c_i) + ΣΣN(c_i c_j) - ΣΣΣN(c_i c_j c_k) 1≦i≦t 1≦i<j≦t 1≦i<j<k≦t + ... + (-1)^t N(c_1 c_2 ... c_t). (10%) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.217.34.144 ※ 编辑: suhorng 来自: 61.217.34.144 (04/02 19:37)