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

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.46 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1396064280.A.843.html