MATH2069/2969 Semester 1 Main, 2019 page 2 of 11 SECTION A: Discrete Mathematics Use separate writing booklets for sections A and B. 1. A group of 30 people get together to start a small company. (a) How many different ways can they elect a managing committee of 8 people, including 2 people appointed as co-presidents? Solution: We could count the ways to select a subset of 8 people out of 30, and then select a subset of 2 people out of the chosen 8, which gives us ( 30 8 )( 8 2 ) ways of making this selection. Alternatively, we could count the ways to select a subset of 2 people (the co-presidents) out of 30, and then select a subset of 6 additional people out of the remaining 28, which gives us ( 30 2 )( 28 6 ) ways of making this selection. (b) 100 indistinguishable cards are printed with the company name and logo. What is the number of ways to distribute the cards among the 30 employees, given that everyone must have at least 2 cards? Solution: First give two card to everyone, and then distribute the remain- ing 100− 2(3) = 40 cards. The number of ways to distribute the remaining 40 identical cards among 30 employees is ( 30 + 40− 1 40 ) = ( 69 40 ) . (c) In their new building, there are 10 offices, so exactly 3 people will be assigned to each office. How many ways are there to assign an office to each employee? Solution: Numbering the offices 1, 2, . . . , 10, we successively select 3 people for each, giving us ( 30 3,3,3,3,3,3,3,3,3,3 ) = 30! (3!)10 ways to assign the offices. (d) There are 5 priority projects that the company needs to work on. How many ways are there to assign an employee to each task, so that each task has at least one person working on it? Solution: This is the number of surjective functions from a set of cardi- nality 30 to a set of cardinality 5 and so equals 5!S(30, 5). 2. (a) Write the characteristic polynomial of the recurrence relation bn = bn−1 + 12 bn−2, where n > 2. Solution: The characteristic polynomials is x2 − x− 12. (b) Find the general solution of the recurrence relation bn = bn−1 + 12 bn−2, where n > 2. Solution: The characteristic equation is x2 − x− 12 = (x− 4)(x+3) = 0. Hence the general solution of the recurrence relation is bn = A (4) n+B (−3)n, where A and B are arbitrary constants. SOLUTIONS turn to page 3 MATH2069/2969 Semester 1 Main, 2019 page 3 of 11 (c) Find one particular solution of the recurrence relation an = an−1 + 12 an−2 − 4 n, where n > 2. Solution: Since 4 is a root of the characteristic polynomial with multi- plicity 1, we will look for a particular solution in the form pn = Cn(4) n. Substituting this into the relation, we get Cn(4)n = C(n− 1)(4)n−1 + 12C(n− 2)(4)n−2 − (4)n. Dividing both sides by (4)n−1 we get 4Cn = Cn− C + 3Cn− 6C − 4. Equating the coefficients of n and the constant terms we get C = C and 0 = −C − 6C − 4, and so C = −4 7 . Therefore, a particular solution of the recurrence relation is an = −4n 7 (4)n. (d) Find the solution of the recurrence relation an = an−1 + 12 an−2 − 4 n, where n > 2, satisfying the initial conditions a0 = 0 and a1 = −2. Solution: Taking n = 0 and n = 1 we get A+B = 0 and 4A−3B− 16 7 = −2. Hence A = −B = 2 49 and the solution is an = 2 49 (4)n − 2 49 (−3)n − 4 7 (n) (4)n. SOLUTIONS turn to page 4 MATH2069/2969 Semester 1 Main, 2019 page 4 of 11 3. This question is for MATH2069 students only. (a) The generating function of a sequence an is given by the formula A(z) = 3 + z (1 + 2z)2 . Write down an explicit formula for an. Solution: By a result from lectures, an = 3(n+ 1)(−2) n + (n)(−2)n−1. (b) Let bn = a0an + a1an−1 + · · · + ana0. Find a closed form for the generating function B(z) for the sequence bn. Solution: We can identify the bn as the coefficients of z n in A(z)2.. Thus: B(z) = ( 3 + z (1 + 2z)2 )2 = (3 + z)2 (1 + 2z)4 . (c) Let cn = a0 + a1 + · · ·+ an. Find a closed form for the generating function C(z) for the sequence cn. Solution: By a result from lecture: C(z) = ( A(z) (1− z) ) = 3 + z (1− z)(1 + 2z)2 . (d) Express the generating function for the sequence 2,−3, 4,−5, 6,−7, . . . in the form P (z) Q(z) , where P (z) and Q(z) are both polynomials. Solution: We have an = (−1) n(n+ 2) and so A(z) = ∞∑ n=0 (−1)n(n+ 2)zn = ∞∑ n=0 (n+ 1 + 1)(−z)n = 1 (1 + z)2 + 1 1 + z which equals z + 2 (1 + z)2 . 3. This question is for MATH2969 students only. (a) Let B(z) = ∑ ∞ n=0 bnz n = log(1 + z) be defined as the unique formal power series such that B′(z) = 1 1+z , with b0 = 0. Write down a closed form for bn. Solution: Since the derivative of log(1 + z) is 1 1+z , we can find the co- efficients of B(z) by integrating the formal power series of 1 1+z . We thus get B(z) = ∞∑ n=1 (−1)nzn n . SOLUTIONS turn to page 5 MATH2069/2969 Semester 1 Main, 2019 page 5 of 11 (b) Recall that exp(z) = ∑ ∞ n=0 zn n! . Let F (z) be a given formal power series and let G(z) be the unique formal power series with zero constant term such that G′(z) = F (z). Prove that for a given value of a0, the differential equation A ′(z) = F (z)A(z) has a unique solution which is given by A(z) = a0 exp ( G(z) ) . Solution: Verify first that A(z) = a0 exp ( G(z) ) is indeed a solution of the equation A′(z) = F (z)A(z). Use the chain rule:( a0 exp ( G(z) )) ′ = a0 exp ( G(z) ) G′(z) = a0 exp ( G(z) ) F (z). Since the constant term of exp ( G(z) ) is 1, the constant term of a0 exp ( G(z) ) is indeed a0. Now demonstrate that a0 exp ( G(z) ) is the unique solution of the equation with constant term a0. It is enough to prove that, given any number a0 and any power series F (z) = ∑ ∞ n=0 bn z n, there is a unique way to choose a1, a2, a3, · · · so that the power series A(z) = ∑ ∞ n=0 an z n satisfies the equation A′(z) = F (z)A(z). Extracting the zn term from both sides of this equation, we see that it is equivalent to (n+ 1)an+1 = n∑ m=0 bman−m, for all n ≥ 0, which is a recurrence relation determining an+1 in terms of a0, a1, · · · , an and the fixed numbers bm. So it is indeed true that a1, a2, a3, · · · are uniquely determined. (c) Show that the formal power series A(z) = exp ( log(1+2z+z2) ) satisfies the equation A′(z) = A(z) 2 1 + z . Solution: Using the chain rule, we find A′(z) = exp ( log(1+2z+z2) ) 1 1 + 2z + z2 (2+2z) = A(z) 2(1 + z) (1 + z)2 = A(z) 2 1 + z , as required. (d) Using the previous results, prove the identity exp ( log(1 + 2z + z2) ) = 1 + 2z + z2. Solution: The formal power series A(z) = 1 + 2z + z2 is a solution of the equation in part (b). To apply the result in part (b), we need to verify that the constant term of the series exp ( log(1 + 2z + z2) ) is 1. By part (a), log(1 + 2z + z2) = 2z + z2 − (2z + z2)2 2 + . . . , and in particular the constant term is 0. Since exp z = 1 + z + . . . , the constant term of exp ( log(1 + z + z2) ) is indeed 1, as required. SOLUTIONS turn to page 6 MATH2069/2969 Semester 1 Main, 2019 page 6 of 11 SECTION B: Graph Theory Use separate writing booklets for sections A and B. 4. (a) Only one of the sequences (3, 3, 3, 3, 4, 5), (3, 3, 4, 4, 4, 6), and (3, 3, 3, 3, 4, 4) is graphic. Explain why two of these sequences are not graphic. Solution: As a consequence of the Hand-shaking Lemma, the sum of degrees of all vertices of a graph must be even. Therefore the first sequence is not graphic. The second sequence is not graphic because otherwise the degree of one vertex would be equal to 6, while the number of remaining vertices is 5. (b) Draw a picture of a graph whose degree sequence coincides with the remain- ing sequence in part (a). Solution: (c) Either write down an Eulerian trail in the following graph, or explain why none exists. a b e g h c d f i j Solution: An Eulerian trail is b, a, f, e, g, h, i, c, f, i, j, f, d, c, h, e, b, c. 5. (a) Complete the formulation of the Travelling Salesman Problem: “Given a connected weighted graph, find a walk which . . . ”. Solution: Given a connected weighted graph, find a walk which visits every vertex, returns to its starting point, and has minimum weight subject to these two conditions. (b) Find a walk which solves the Travelling Salesman Problem for the following weighted graph. Justify your answer. a b c e f d 8 17 17 8 11 4 5 10 6 SOLUTIONS turn to page 7 MATH2069/2969 Semester 1 Main, 2019 page 7 of 11 Solution: The walk a, b, c, d, c, f, e, b, a of weight 61 is a solution. The distance from a to d is 30, the distance from d to e is 15 and the distance from e to a is 16. Hence the weight of a solution of the Travelling Salesman Problem cannot be less than 30 + 15 + 16 = 61. (c) Find a minimal spanning tree for the weighted graph in (b). Solution: Prim’s algorithm yields a unique solution: a b c e f d 8 8 4 5 6 (d) Consider the trees with 7 vertices {1, 2, 3, 4, 5, 6, 7} which have a vertex of degree 4. (i) What is the possible number of leaves in such a tree? Solution: Let (d1, . . . , d7) be the degree sequence of such a tree. Since it has 6 edges we have d1 + · · ·+ d7 = 12. We must have d7 = 4 so that d1 + · · · + d6 = 8. Since all degrees are positive integers, we have only two possibilities d1 = · · · = d5 = 1 and d6 = 3, or d1 = · · · = d4 = 1 and d5 = d6 = 2. Such trees do exist: for example, take Pru¨fer sequences (1, 1, 2, 2, 2) and (1, 2, 3, 3, 3). Hence the possible number of leaves is 4 or 5. (ii) What is the number of isomorphism classes of such trees? Solution: There are three isomorphism classes. Label the vertex of degree 4 by a. It must be adjacent to 4 other vertices which we denote by b, c, d and e. There are two more vertices, say, f and g. Since the graph is connected, f or g should be adjacent to one of the 4 vertices b, c, d or e. Re-labelling vertices if necessary, we may assume that f is adjacent to b. Now, there are 3 choices (up to isomorphism): g can be adjacent to a, to b or to f . The three trees are pairwise non-isomorphic: the first contains a vertex of degree 3, the third has a path of length 4. Justify your answer to each of the questions. (e) A tree has two vertices of degree 4. What is the minimum possible number of vertices in such a tree? Justify your answer. Solution: Let the two vertices of degree 4 be 1 and 2. Then each of 1 and 2 will occur in the Pru¨fer sequence of such a tree three times. Hence, the total number of vertices cannot be less than 8. Such trees with 8 vertices do exist: take vertices 1, 2, 3, 4, 5, 6, 7, 8 and the Pru¨fer sequence (1, 1, 1, 2, 2, 2). SOLUTIONS turn to page 8 MATH2069/2969 Semester 1 Main, 2019 page 8 of 11 6. This question is for MATH2069 students only. (a) Let t be a natural number. Define what is meant for a graph G to be t- colourable. Solution: A graph G is t-colourable if there exists a vertex colouring of G with t colours so that no two adjacent vertices have the same colour. (b) Use mathematical induction on the number n of vertices in G to show that any graph G is t-colourable for t = ∆(G) + 1. Solution: In the case where G is a single vertex we have ∆(G) = 0, and G is indeed 1-colourable. So we can assume that n > 2 and that the result is true for graphs with fewer than n vertices. Let v be any vertex of G. It is clear that ∆(G − v) 6 ∆(G), so the induction hypothesis implies that G− v is (∆(G) + 1)- colourable; choose a vertex colouring of G−v where the colour set has size ∆(G)+1. Now the number of vertices of G adjacent to v is deg(v), which is at most ∆(G) by definition. So at most ∆(G) different colours are used among the vertices adjacent to v. Therefore there is a colour which is not used among these vertices, and we can colour v with this colour to obtain a vertex colouring of G. The induction step is complete. (c) The graph H is given by the picture (i) What is the maximum possible value of the chromatic number χ(H) as provided by the Brooks Theorem? Solution: Since the graph is neither complete nor an odd cycle, its chro- matic number χ(H) does not exceed ∆(H) = 4. (ii) What is the exact value of χ(H)? Justify your answer. Solution: Since the graph contains 3-cycles, its chromatic number is at least 3. On the other hand, 3 colours are sufficient to get a vertex colouring: assign one colour to each pair of opposite vertices. Hence, χ(H) = 3. (iii) What are the possible values of the edge chromatic number χ′(H) as provided by the Vizing Theorem? Solution: Since ∆(H) = 4, the possible values of the edge chromatic number χ′(H) are 4 and 5. (iv) What is the exact value of χ′(H)? Justify your answer. Solution: We will show that χ′(H) = 4 by producing an edge colouring with 4 colours. Give the respective labels 1, 2, 3, 4, 5, 6 to the vertices starting with the top vertex 1 and proceeding clockwise. Colour the edges {1, 2}, {3, 5}, {4, 6} red, the edges {1, 3}, {2, 4}, {5, 6} blue, the edges {1, 5}, {2, 6}, {3, 4} yellow, and the edges {1, 6}, {2, 3}, {4, 5} white. SOLUTIONS turn to page 9 MATH2069/2969 Semester 1 Main, 2019 page 9 of 11 6. This question is for MATH2969 students only. (a) For any n > 6 the graph Gn can be drawn as a regular polygon with n vertices together with all diagonals of the minimal length. [ For instance, the picture above on this page represents Gn for n = 6 ]. (i) Calculate the chromatic numbers χ(Gn). Justify your answer. Solution: Since the graph contains 3-cycles, its chromatic number is at least 3. On the other hand, by the Brooks theorem, χ(Gn) does not exceed ∆(Gn) = 4. We will show that χ(Gn) = 3 if n is a multiple of 3, and χ(Gn) = 4 otherwise. Give the respective labels 1, 2, . . . , n to the vertices starting with a certain vertex 1 and proceeding clockwise. Suppose that n = 3k for an integer k > 2. Colour the vertices 1, 4, . . . , 3k− 2 red, the vertices 2, 5, . . . , 3k− 1 blue and the vertices 3, 6, . . . , 3k white. This yields a proper vertex colouring so that χ(G3k) = 3. Now let n = 3k + 1 or n = 3k + 2 for an integer k > 2. We suppose that χ(Gn) = 3 and will come to a contradiction. The 3-cycle 1, 2, 3 requires 3 colours so choose red for vertex 1, blue for vertex 2 and white for vertex 3. Since we cannot use any extra colours, the colours of all remaining vertices are then uniquely determined: we must colour vertex 4 red, vertex 5 blue, vertex 6 white, etc. Thus, the vertices of the form 3m+1, 3m+2 and 3m+3 with m > 0 must have respective colours red, blue and white. This makes a contradiction since one of the vertices n− 1 or n− 2 adjacent to vertex 1 will have the same colour as 1. (ii) Calculate the edge chromatic number χ′(G8). Justify your answer. Solution: Since ∆(G8) = 4, by the Vizing Theorem the possible values of the edge chromatic number χ′(G8) are 4 and 5. We will show that χ ′(G8) = 4 by producing an edge colouring with 4 colours. Give the respective labels 1, 2, 3, 4, 5, 6, 7, 8 as in the solution of the previous part. Colour the edges {1, 2}, {3, 4}, {5, 6}, {7, 8} red, the edges {1, 3}, {2, 8}, {4, 6}, {5, 7} blue, the edges {1, 7}, {2, 4}, {3, 5}, {6, 8} yellow, and the edges {1, 8}, {2, 3}, {4, 5}, {6, 7} white. (iii) Prove that if n is odd then χ′(Gn) = 5. Solution: By the Vizing Theorem, the possible values of the edge chro- matic number χ′(Gn) are 4 and 5. We will show that an edge colouring with 4 colours is impossible. By the Hand-shaking Lemma, the number of edges is 2n. On the other hand, the maximum number of edges with the same colour is (n − 1)/2. Hence, if only four different colours are used, then the number of coloured edges would not exceed 4 · (n−1)/2 = 2n−2. Therefore, 4 colours are not sufficient and so χ′(Gn) = 5. SOLUTIONS turn to page 10 MATH2069/2969 Semester 1 Main, 2019 page 10 of 11 (b) Find the chromatic polynomial for the graph Solution: There is only one pair of non-adjacent vertices in the given graph G, which we denote by v and w. The graph G+ {v, w} is isomorphic to the complete graph K6 while the graph G[v, w] is isomorphic to K5. Hence, by a theorem from lectures, PG(t) = PK6(t) + PK5(t) = t(t− 1)(t− 2)(t− 3)(t− 4)(t− 5) + t(t− 1)(t− 2)(t− 3)(t− 4) = t(t− 1)(t− 2)(t− 3)(t− 4)2. SOLUTIONS turn to page 11 MATH2069/2969 Semester 1 Main, 2019 page 11 of 11 SOLUTIONS This is the end of the examination paper



































































































































































































































































































































































































































































































学霸联盟