課程名稱︰離散數學 課程性質︰選修 課程教師：呂育道 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰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. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.57.98 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1480485610.A.B17.html ※ 編輯: rod24574575 (118.160.57.98), 11/30/2016 14:01:01