課程名稱︰離散數學
課程性質︰選修
課程教師：呂育道
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2016.05.12
考試時限（分鐘）：
試題 :
Discrete Mathematics
Examination on May 12, 2016
Spring Semester, 2016
Problem 1 (20 points)
Solve the following recurrence relations:
1) (10 points) a_n - 10 a_(n-1) + 25 a_(n-2) = 8 × 5^n with a_0 = 6 and
a_1 = 10.
2) (10 points) a_(n+2) = a_(n+1) a_n with a_0 = 1 and a_1 = 2.
Ans: 1) (4n^2 - 8n + 6)5^n, n ≧ 0.
1 ╭ 1 + √5 ╮n 1 ╭ 1 - √5 ╮n
2) a_n = 2^(F_n), where F_n =───│──── │ -───│──── │
√5 ╰ 2 ╯ √5 ╰ 2 ╯
Problem 2 (10 points)
Let G = (V_1, V_2, E) be a connected bipartite undirected graph. Show that
if |V_1| ≠ |V_2|, then G has no Hamiltonian cycles.
Ans: The nodes on a Hamiltonian cycle in G must alternate between nodes in V_1
and those in V_2 as G is bipartite. As the cycle must exhaust all nodes,
|V_1| = |V_2|.
Problem 3 (10 points)
Let (V, E) be a tree. Show that |V| = |E| + 1.
Ans: See p. 679 of the slides.
Problem 4 (10 points)
Find the coefficient of x^47 in f(x) = (x^5 + x^8 + x^11 + x^14 + x^17)^4.
∞╭ n + i - 1 ╮ i
(Recall (1 - x)^(-n) = Σ│ │x .)
i=0╰ i ╯
Ans: f(x) = x^20 (1 + x^3 + x^6 + x^9 + x^12)^4
╭ 1 - x^15 ╮4
= x^20│ ──── │
╰ 1 - x^3 ╯
= x^20 (1 - x^15)^4 (1 - x^3)^(-4)
╭ ∞╭ 4 + i - 1 ╮ 3i ╮
= x^20 (1 - 4x^15 + 6x^30 - 4x^45 + x^60)│ Σ│ │x │
╰ i=0╰ i ╯ ╯
╭ 12 ╮ ╭ 7 ╮
The coefficient of x^47 = │ │ - 4│ │ = 220 - 140 - 80
╰ 9 ╯ ╰ 4 ╯
Problem 5 (10 points)
What is the largest value of n for which K_(6,n) is planar?
Ans: It is easy to see that K_(6,1) and K_(6,2) are planar. Since K_(3,3) is
a subgraph of K_(6,3) and K_(3,3) is not planar, K_(6,3) is not planar.
Hence the largest value of n is 2.
Problem 6 (10 points)
Use the generating function to solve the number of integer solutions for the
following linear equation
x_1 + x_2 + x_3 + x_4 = 8
where 0 ≦ x_i ≦ 7, for all 1 ≦ i ≦ 4. Expressing the answer in terms of
binomial coefficients is fine.
∞╭ n + i - 1 ╮ i
(Recall (1 - x)^(-n) = Σ│ │x .)
i=0╰ i ╯
Ans: Note that
f(x) = (x^0 + x^1 + x^2 + … + x^7)^4
╭ 1 - x^8 ╮4
= │──── │
╰ 1 - x ╯
= (1 - x^8)^4 (1 - x)^(-4)
╭ ∞╭ 4 + i - 1 ╮ i ╮
= (1 - 4x^8 + 6x^16 - 4x^24 + x^32)│ Σ│ │x │
╰ i=0╰ i ╯ ╯
The desired number is the coefficient of x^8, which is equal to
╭ 4 + 8 - 1 ╮ ╭ 4 + 0 - 1 ╮ ╭ 11 ╮ ╭ 3 ╮
│ │ - 4│ │ = │ │ - 4│ │ = 161
╰ 8 ╯ ╰ 0 ╯ ╰ 8 ╯ ╰ 0 ╯
Problem 7 (10 points)
Use generating function to find the convolution of the following two sequences:
1, 1, 1, 1, 1, 1 and 1, 1, 1.
Ans: The generating function of 1, 1, 1, 1, 1, 1 is
A(x) = 1 + x + x^2 + x^3 + x^4 + x^5,
and the generating function of 1, 1, 1 is
B(x) = 1 + x + x^2.
Let C(x) be the generating function of their convolution. Then
C(x) = A(x)B(x) = 1 + 2x + 3x^2 + 3x^3 + 3x^4 + 3x^5 + 2x^6 + x^7.
So the convolution of these two sequences is 1, 2, 3, 3, 3, 3, 2, 1.
Problem 8 (10 points)
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.
Ans: Every partition can be represented by a Ferrer's graph, shown below. Note
that the number of dots per row in a Ferrer's graph does not increase as
we go from the top to the bottom.
˙˙˙˙ ˙˙˙˙˙
˙˙˙˙ Transpose ˙˙˙˙˙
˙˙˙ ─────→ ˙˙˙
˙˙ ˙˙
˙˙
15 = 4 + 4 + 3 + 2 + 2 15 = 5 + 5 + 3 + 2
5 summands 5 is the largest summand
There is a one-to-one correspondence between a Ferrer's graph and its
transposition.
Problem 9 (10 points) _
If G is a simple graph with 20 edges and G has 16 edges, how many vertices
does G have?
Ans: Assume that the number of vertices of G is n, then
╭ n ╮ n(n-1)
20 + 16 = │ │ = ────
╰ 2 ╯ 2
This implies that n^2 - n - 72 = 0. Hence (n - 9)(n + 8) = 0. So n = 9.