MATH2069/2969 Discrete Mathematics Semester 1 Main, 2019

1.   A group of 30 people get together to start a small company.

(a)  How many dierent ways can they elect a managing committee of 8 people, including 2 people appointed as co-presidents?

(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?

(c)  In their new building, there are 10 oces, so exactly 3 people will be assigned to each oce. How many ways are there to assign an oce to each employee?

(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?

2.      (a)  Write the characteristic polynomial of the recurrence relation bn  = bn−1 + 12 bn−2, where n > 2.

(b)  Find the general solution of the recurrence relation

bn  = bn−1 + 12 bn−2, where n > 2.

(c)  Find one particular solution of the recurrence relation an  = an−1 + 12 an−2  4n , where n > 2.

(d)  Find the solution of the recurrence relation

an  = an−1 + 12 an−2  4n , where n > 2,

satisfying the initial conditions a0  = 0 and a1  =    2.

A(z) =

Write down an explicit formula for an .

(b)  Let bn  = a0 an + a1 an−1 +    + an a0 . Find a closed form for the generating function B(z) for the sequence bn .

(c)  Let cn  = a0 + a1 +    + an . Find a closed form for the generating function

C(z) for the sequence cn .

(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.

3.   This question is for MATH2969 students only.

(a)  Let B(z) = P bn zn  = log(1 + z) be de  ned as the unique formal power series such that B′ (z) = , with b0  = 0. Write down a closed form for bn .

(b)  Recall that exp(z) =   znn! .

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 dierential equation A′ (z) = F(z)A(z) has a unique solution which is given by A(z) = a0 exp  G(z)  .

(c)  Show that the formal power series A(z) = exp   log(1+2z+z2 )  satis  es the

equation A′ (z) = A(z)    2   

(d)  Using the previous results, prove the identity exp   log(1 + 2z + z2 )  = 1 + 2z + z2 .

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.

(b)  Draw a picture of a graph whose degree sequence coincides with the remain-

ing sequence in part (a).

(c)  Either write down an Eulerian trail in the following graph, or explain why

none exists.                               a             b        c

                                  d

h                      i

5.      (a)  Complete the formulation of the Travelling Salesman Problem:   “Given a connected weighted graph,   nd a walk which ... ” .

(b)  Find a walk which solves the Travelling Salesman Problem for the following weighted graph. Justify your answer.

(c)  Find a minimal spanning tree for the weighted graph in (b). Solution:   Prim’s algorithm yields a unique solution:

b                c

8

8

e       6           f

(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?

(ii)  What is the number of isomorphism classes of such trees?                 

(e)  A tree has two vertices of degree 4. What is the minimum possible number of vertices in such a tree? Justify your answer.

6.   This question is for MATH2069 students only.

(a)  Let t be a natural number.  De  ne what is meant for a graph G to be t- colourable.

(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.

(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?

(ii)  What is the exact value of ⃞(H)? Justify your answer.

(iii)  What are the possible values of the edge chromatic number ⃞′ (H) as provided by the Vizing Theorem?

(iv)  What is the exact value of ⃞′ (H)? Justify your answer.

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.

(ii)  Calculate the edge chromatic number ⃞′ (G8 ). Justify your answer.

(iii)  Prove that if n is odd then ⃞′ (Gn ) = 5.

(b)  Find the chromatic polynomial for the graph