课程名称︰离散数学 课程性质︰必修 课程教师︰陈健辉 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2010.10.28 考试时限（分钟）：120 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Solutions to Examination #1 (范围:Combinatorics) (For each problem, please provide your computation details, not only your answer.) 1.Find a recurrence relation for the number of distinct outputs that may be generated from the following stack. You are REQUIRED to explain your answer, but NOT REQUIRED to solve the relation. (10%) Output ← ←1, 2, ., ..., n Input ↑ ↓ Stack Sol:Refer to pages 137-138 of lecture notes. 2.How many four-element subsets of {1, 2, ..., 15} are there that contain no cconsecutive integers? (10%) Sol:Refer to pages 62-63 of lecture notes. 3.Compute the number of ways to tile a 2 x n chessboard using horizontal 1 x 2 dominoes (which can also be used as vertical 2 x 1 dominoes) and aquare 2 x 2 tiles. (10%) Sol.Clearly, a[1] = 1 and a[2] = 3. When n >= 3, let us consider the rightmost column of the chessboard. If it is covered by one vertical(2 x 1) domino, then a[n] = a[n-1]. If it is covered by two horizontal (1 x 2) dominos, then a[n] = a[n-2]. If it is covered by one square (2 x 2) title, then a[n] = a[n-2]. Hence, a[n] = a[n-1] + 2a[n-2]. characteristic equation: r^2 - r - 2 = 0. characteristic roots: 2, -1. general solution: a[n] = c[1](-1)^n + c[2](s)^n. a[1] = 1: (-1)c[1] + 2c[2] = 1. s[2] = 3: c[1] + 4c[2] = 3. →c[1] = 1/3, c[2] = 2/3. Therefore, a[n] = (1/3)(-1)^n + (2/3)(s)^n, n >= 1. 4.Show that 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%) Sol:Refer to pages 69-70 of lecture notes. 5.At a 12-week conference, Sharon met seven of her friends. During the conference she met each friend at lunch 35 times, every pair of them 16 times, every trio eight times, every foursome four times, each set of five twice, and each set of six once, but never all seven at once. If she had luncg every day during the 84 days of the conference, did she ever have lunch alone? (10%) Sol.Denote Sharon's seven friends by f[1], f[2], ..., f[7]. Let c[i] be the condition that Sharon and f[i] had lunch together. Then, the number of days Sharon had lunch alone is N(c'[1]c'[2]c'[3]c'[4]c'[5]c'[6]c'[7]) = 84 - c(7,1)x35 + c(7,2)x16 -c(7,3)x8 + c(7,4)x4 - c(7,5)x2 + c(7,6)x1 = 0. 6.The number pf 20-digit quaternary (0, 1, 2, 3) sequences that contain at least one 2 and an odd number of 0's can be expressed as a x 4^20 + b x 3^20 +c x 2^20 + d. What are a,b,c, and d? (10%) Sol. The number of 20-digit quaternary (0, 1, 2, 3) sequences that contain at least one 2 and an odd number of 0's us tge cieffucuent of (x^20)/20! in the following generating function: (x + x^2/2! + x^3/3! +... + x^19/19!) x (x + x^3/3! + x^5/5! + ... + x^19/19!) x (a + x + x^2/2! + x^3/3! + ... + x^18/18!)^2 = (e^x - 1) x (e^x - e^(-x))/2 x e^(2x) = 1/2 x (e^4x - e^3x - e^2x + e^x), which is 1/2 x (4^20 - 3^20 - 2^20 + 1). a = d = 1/2, b = c = -1/2 7.Solve a[n] - 2a[n-1] = 4^(n-1), where n >= 1 and a[0] = 1, by the method of generating functions. (10%) Sol:Refer to page 132 of lecture notes. 8.In how many ways can two dozen identical robots be assigned to four assembly lines with at least three, but no more than nine, robots assigned to each line? (10%) Sol.The answer is the coefficient of x^24 in (x^3 + x^4 + ... + x^9)^4 = x^12(1 + x + x^2 + ... + x^6)^4, where (1 + x + x^2 + ... + x^6)^4 = [(1-x)^7/(1-x)]^4 = (1-x^7)^4(1-x)^(-4). The coefficient of x^12 in (1-x^7)^4(1-x)^(-4) is equal to (4)(-1)^5 c(8,5) + c(15,12) = 231 9.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 word 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%) Sol: r(C2,x) = 1 + 4x + 2x^2. r(C,x) = (1 + 4x + 3x^2)(1 + 4x + 2x^2) = 1 + 8x + 21x^2 + 20x^3 + 6x^4 Let ci be the condition of assigning Grader-i with a course that he or she dislikes. Then N(c1'c2'c3'c4'c5') = 5! - 8 x 4! + 21 x 3! - 20 x 2! + 6 x 1! = 20. 10.For the binary string 001110, there are three runs: 00, 111, and 0. Meanwhile, the string 000111 has only two runs: 000 and 111; wguke tge string 010101 determines the six runs: 0, 1, 0, 1, 0, 1. For n = 1, we consider two binary strings, namely 0 and 1; these two strings (of length 1) determine a total of two runs. There are four binary strings of length n = 2 and these strings determine 1 (for 00) + 2(for 01)+ 2 (for 10) + 1(for 11) = 6 runs. Find the number of runs determined by the 2^n binary strings of length n, where n >= 1. (10%) Sol,Let tn be the number of runs determined by the 2^n binary strings of length n. Consider the 2^(n-1) binary strings of length n that end with 0. Since half of these 2^(n-1) binary strings end with 1, there are t[n-1] + (1/2)(2^(n-1)) runs. Similarly, the 2^(n-1) binary strings of length n that end with 1 determines the same number of runs. Therefore, we have t[n] = 2t[n-1] + 2^(n-1), where n >= 2. Since tnh = c(2^n), we assume tnp = kn(2^n). Thus, kn(2^n) = 2k(n-1)2^(n-1) + 2^(n-1) = kn(2^n) - k(2^n) + 2^(n-1), from which k = 1/2 is determined. Consequently, tn = tnh + tnp = c(2^n) + n(2^(n-1)). Since t1 = 2, we have c = 1/2. So, tn = (1/2)2^n + n(2^(n-1)) = (n+1)(2^(n-1)), where n >= 1. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.98