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