课程名称︰离散数学 课程性质︰选修 课程教师︰陈健辉 开课学院：电机资讯学院 开课系所︰资工系 考试日期（年月日）︰2011/4/12 考试时限（分钟）：2小时 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Examination #1 (范围:Combinatorics) (For each problem, please provide your computation details, not only your answer.) 1. Solve the following recurrence relations.(10%) a(n+3) - 3a(n+2) + 3a(n+1) - a(n) = 3 + 5n, n>=0. 2. Suppose that n is a nonnegative integer. Find the generating function for the number of ways to partition n into summands such that: (a) each summand must appear an even number of times. (5%) (b) each summand must be even. (5%) 3. Find the number of integer solutions to x1 + x2 + x3 + x4 = 19, where -5 <= xi <= 10 for 1 <= i <= 4.(10%) 4. In how many ways can a sequence of 1's and 2's sum to n, where n >= 0?(10%) 5. How can Mary split up 12 hanbergers and 16 hot dogs among her sons Richard, Peter, Christopher, and James in such a way that James gets at least one hambergers and three hot dogs, and each of his brothers gets at least two hambergers but at most five hot dogs? (10%) 6. 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 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? (10%) 7. Why is the coefficient of x^4/4! in (1+x+x^2/2!)^2(1+x)^2 the number of ways to arange four letters from ENGINE? (10%) ╴╴ ╴ 8. Prove N(c1c2...ct) = N - Σ N(ci) + Σ N(cicj) - Σ N(cicjck) + ... 1≦i≦t 1≦i<j≦t 1≦i<j<k≦t + (-1)^t N(c1c2...ct), not by induction. (10%) 9. Explan why a recurrence relation of the form a(n)=a(0)a(n-1)+a(1)a(n-2)+... +a(n-1)a(0) can be used to compute the number of distinct outputs that may be generated from the following stack. You are NOT REQUIRED to solve the relation. (10%) ────────────╮╭──────────────── ││ Output ← ││ ← 1, 2, 3, ... , n Input ──────────╮ ╰╯ ╭─────────────── │↑ ↓│ │ │ │ │ │ │Stack │ │ │ │ ╰────╯ 10. Let a(n) count the number of ways to write n as an ordered sum of odd positive integers, where n >= 1. For example, a(3)=2 (because 3=3=1+1+1) and a(4)=3 (because 4=3+1=1+3=1+1+1+1), Verify a(n) = a(n-1) + a(n-2) for n >= 3. (10%) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.129 ※ 编辑: fei6409 来自: 140.112.30.129 (04/12 20:36) 修改一点错字。 ※ 编辑: fei6409 来自: 118.168.235.198 (04/12 22:51)