課程名稱︰離散數學
課程性質︰系必修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰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