推 andy74139 :已收錄至精華區!! 04/12 22:14
修改一點錯字。
※ 編輯: fei6409 來自: 118.168.235.198 (04/12 22:51)
推 andy74139 :已重新收錄!! 04/15 17:24
課程名稱︰離散數學
課程性質︰選修
課程教師︰陳健輝
開課學院：電機資訊學院
開課系所︰資工系
考試日期（年月日）︰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)