課程名稱︰離散數學 課程性質︰資訊系選修 課程教師︰陳健輝 開課學院：電資學院 開課系所︰資訊系 考試日期（年月日）︰2013/03/27 考試時限（分鐘）：150 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Examination #1 (範圍: Combinatorics) (For each problem (except problem 9), please provide computation details, not the answer only.) 1. Professor Ruth has four graders to correct programs in her four courses: Java, C++, SQL, and Perl. Grader Jeanne dislikes SQL, and Sandra wants to avoid SQL and Java. Grader Charles refuses to work in Perl and C++, and Paul refuses to work in Perl. In how many ways can Professor Ruth assign each grader to correct programs in one language, cover all four languages , and keep everyone content? (10%) 2. Find the number of derangements of 1, 2, ..., 6. (10%) 3. Given a finite set S and four conditions c_1, c_2, c_3, c_4 on the elements of S, the equality ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ N(c_2 c_3 c_4) = N(c_1 c_2 c_3 c_4) + N(c_1 c_2 c_3 c_4) can be verified by showing that its two sides count the same for each element x of S. You may consider the number of conditions that are satisfied by x. Please provide a combinatorial proof for the equality. (10%) 4. How many 6-digit ternary (0, 1, 2) sequences are there where there are exactly two 0's or none at all? (10%) 5. In how many ways can a police captain distribute 24 rifle shells to five police officers so that each gets at least four shells, but not more than seven? (10%) 6. Find the number of ways to arrange three of the letters from CIVIC by the method of generating function. (10%) 7. In how many ways can 24 identical robots be assigned to four assembly lines with at least three robots assigned to each line? (10%) 8. For n ≧ 1, let a_n count the number of ways to tile a 2 x n chessboard using horizontal 1 x 2 (or vertical 2 x 1) dominoes and square 2 x 2 tiles. Find and solve a recurrence relation for a_n. (10%) 9. Consider the following two recurrence relations. R1: a_n - 10a_{n-1} + 21a_{n-2} = f_1(n) , where n ≧ 2 R2: a_n + 4a_{n-1} + 4a_{n-2} = f_2(n) , where n ≧ 2 Write the forms of (a_n)^p 's for R1 when f_1(n) = 5 , 7 x 11^n and 2 x 3^n - 8 x 9^n , and for R2 when f_2(n) = 5 x (-2)^n and -11 x n^2 x (-2)^n. (10%) 10. Solve a_n - 2a_{n-1} = 4^(n-1) , where n ≧ 1 , using generating function. (10%) 11. Consider the problem of Hanoi towers with n = 4. Let D_1, D_2, D_3, D_4 denote the four disks from top to bottom and P_1, P_2, P_3 denote peg 1, peg 2, peg 3, respectively.The following procedure, with some steps omitted, can transfer D_1 , D_2 , D_3 , D_4 from P_1 to P_3, where "Dk : P_i → P_j" means " move D_k from P_i to P_j". Please complete the procedure by providing the details of the omitted steps. (10%) 12. Consider ternary strings with symbols 0, 1, 2 used. For n ≧ 1, let an count the number of ternary strings of length n, where there are no consecutive 1's and no consecutive 2's. Show a_n = 2a_{n-1} a_{n-2} (Hint : Let a_n(0) , a_n(1) , a_n(2) , be the numbers of ternary strings counted by an whose rightmost symbols are 0 , 1 , 2 respectively.) (10%) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.4.195