课程名称︰离散数学 课程性质︰系必修 课程教师︰陈健辉 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰2008/12/10 考试时限（分钟）：140 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : (范围：Combinatorics) (For each problem, please provide your computation details, not only your answer.) 1. Suggest particular solutions to a[n] + 4*a[n-1] + 4*a[n-2] = f(n), where n >= 2, when (a) f(n) = 5*(-2)^n and (b) f(n) = 7*n*(-2)^n. (10%) 2. In how many ways can the integers 1, 2,..., 10 be arranged in a line so that no even integers is in its natural position? Your answer can be expressed as an arithmetic expression containing, for example, 7! and 5C4. (10%) 3. Professor Ruth has five graders to correct programs in her five courses: Java, C++, SQL, Perl, and VHDL. Graders Jeanne and Charles both dislike SQL, Sandra wants to avoid C++ and VHDL. Paul dislikes Java and C++, and Todd refuses to work 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? Please express your answer as a number, not an arithmetic expression (10%) 4. Compute the number of ways to write an integer n >= 1 as an order sum of positive integers, where each summand is at least 2. For example, a[5] = 3 because 5 can be written as 2+3, 3+2, and 5. (10%) 5. In how many ways can 3000 identical envelopes be divided, in packages of 25, among four student groups so that each group gets at least 150, but not more than 1000, of the envelopes? (10%) 6. Compute the number of ternary ({0, 1, 2}) strings of length n that contain no consecutive 1's and no consecutive 2's, where n >= 1. (10%) 7. How many 20-digit quaternary (0, 1, 2, 3) sequences are there such that no symbol occurs exactly three times? (10%) 8. Prove the principle of inclusion and exclusion, i.e., the number of elements in a set S 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[1]...c[t]) by considering the contribution of every element of S to either side of the equation. (10%) 9. 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%) 10.Prove that the number of ordered rooted binary trees on n vertices is equal to [1/(n+1)]*(2n)C(n). (hint: (1/2x)*(1±sqrt[1-4x]) = (1/2x)((1±)1-Σ(1/2n-1)*(2n)C(n)*x^n))). (10%) --

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