課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2013.05.09
考試時限（分鐘）：
試題 :
Discrete Mathematics
Examination on May 9, 2013
Spring Semester, 2013
Note: You may use any results proved in the class unless stated otherwise.
Problem 1 (10 points)
Let A = {1, 2, 3, 4, 5}.
1) (5 points) How many bijective functions f: A → A satisfy f(1) ≠ 1?
2) (5 points) How many functions f: A → A are invertible?
Ans: 1) 4 × (4!) = 96.
2) 5! = 120.
Problem 2 (10 points)
x^3
Determine the sequence generated by f(x) = ─────.
1 - x^2
x^3
Ans: As f(x) = ───── = (x^3) (1 + x^2 + x^4 + …) = x^3 + x^5 + x^9 + …,
1 - x^2
f(x) generates the sequence {0, 0, 0, 1, 0, 1, 0, …}.
Problem 3 (10 points)
Suppose that n, r ∈ Z+ and 0 ＜ r ≦ n. Prove that
╭ -n ╮ r╭ n + r - 1 ╮
│ │ = (-1) │ │.
╰ r ╯ ╰ r ╯
Ans: See p. 451 of the slides.
Problem 4 (10 points)
Find the generating function and pinpoint the coefficient for the number
of integer solutions to the equation c_1 + c_2 + c_3 + c_4 = 10 where
c_1 ≧ -3, c_2 ≧ -4, -5 ≦ c_3 ≦ 5, and c_4 ≧ 0. (There is no need to
calculate the numerical value of the coefficient. You only have to answer like
"the coefficient of x_i (you specify i) in the generating function … (you
write down the function).")
Ans: Let x_1 = c_1 + 3, x_2 = c_2 + 4, x_3 = c_3 + 5, and x_4 = c4, then the
original problem is equivalent to x_1 + x_2 + x_3 + x_4 = 22 where
x_1, x_2, x_4 ≧ 0, and 0 ≦ x_3 ≦ 10. Consequently, the answer is the
coefficient of x^22 in the generating function
(1 + x + x^2 + …)^3 (1 + x + x^2 + … + x^10).
Problem 5 (10 points)
Let n ∈ Z+.
1) (5 points) Determine ψ(2^n).
2) (5 points) Determine ψ((2^n)p) where p is an odd prime.
Ans: 1) ψ(2^n) = 2^n × (1 - 1/2) = 2^(n-1).
2) ψ((2^n)p) = (2^n)p × (1 - 1/2) × (1 - 1/p) = (2^(n-1))(p-1).
Problem 6 (10 points)
Assume that 11 integers are selected from S = {1, 2, 3, …, 100}. Show that
there are at least two, say x and y, such that 0 < |√x - √y| < 1. (Hint:
You may consider the pigeonhole principle and for any t ∈ S, 0 < √t < 10.)
Ans: For any t ∈ S, 0 < √t < 10, so there must be two integers x and y such
that floor(√x) = floor(√y). Thus, the claim holds.
Problem 7 (10 points)
Suppose |A| = m. How many relations on A are there which are irreflexive and
symmetric?
Ans: For any (x, y) ∈ A and x ≠ y, the number of decisions to make for
╭ m ╮ (m^2 - m) ((m^2 - m)/2)
membership in R is │ │ = ──────. Thus, there are 2
╰ 2 ╯ 2
relations which are irreflexive and symmetric.
Problem 8 (10 points)
Let A = {1, 2, 3} × {1, 2, 3}, and define Ｒ on A by (x_1, y_1)Ｒ(x_2, y_2)
if x_1 + y_1 = x_2 + y_2 for (x_i, y_i) ∈ A.
1) (5 points) Show that Ｒ is an equivalence relation.
2) (5 points) Determine the partition of A induced by Ｒ.
Ans: 1) For all (x, y) ∈ A, x + y = x + y so (x, y)Ｒ(x, y). For
(x_i, y_i) ∈ A, (x_1, y_1)Ｒ(x_2, y_2) implies x_1 + y_1 = x_2 + y_2,
which implies x_2 + y_2 = x_1 + y_1, so (x_2, y_2)Ｒ(x_1, y_1).
(x_1, y_1)Ｒ(x_2, y_2) and (x_2, y_2)Ｒ(x_3, y_3) imply
x_1 + y_1 = x_2 + y_2 and x_2 + y_2 = x_3 + y_3, which implies
x_1 + y_1 = x_3 + y_3, so (x_1, y_1)Ｒ(x_3, y_3). Since Ｒ is
reflexive, symmetric, and transitive, Ｒ is an equivalence relation.
2) A = {(1, 1)} ∪ {(1, 2), (2, 1)} ∪ {(1, 3), (2, 2), (3, 1)} ∪
{(1, 4), (2, 3), (3, 2), (4, 1)} ∪ {(3, 3)}.
Problem 9 (10 points)
Ｒ is said to be a tournament if Ｒ is irreflexive and for all x ≠ y, either
(x, y) ∈ Ｒ or (y, x) ∈ Ｒ. Let Ｒ be a transitive tournament.
1) (5 points) Show that Ｒ has a maximal element.
2) (5 points) Show that Ｒ has a greatest element.
Ans: 1) See p. 302 in the slides.
2) It suffices to show that Ｒ has only one maximal element. Assume that
x and x' are maximal elements in Ｒ and x ≠ x'. For all a ∈ Ｒ,
a ≠ x, (x, a) !∈ Ｒ. Since x' is one of a's, (x, x') !∈ Ｒ.
Similarly, (x', x) !∈ Ｒ. This violates that for all x ≠ y, either
(x, y) ∈ Ｒ or (y, x) ∈ Ｒ. So Ｒ has only one maximal element and
the claim holds. (!∈: 不屬於)
Problem 10 (10 points)
Let S be a set with |S| = N, and c_1, c_2, …, c_t be conditions on the
elements of |S|. N(abc…) denotes the number of elements of S that satisfy
a Λ b Λ c Λ …. Then N(﹁c_1 ﹁c_2 … ﹁c_t) denotes the number of elements
of S that satisfy none of the conditions c_i. Show that
t k
N(﹁c_1 ﹁c_2 … ﹁c_t) = Σ (-1) Σ N(c_i1 c_i2 … c_ik).
k=0 1≦i1＜i2＜…＜ik≦t
Ans: See pp. 366-367 in the slides.