COMP151101
Introduction to Discrete Mathematics
May/June 2018
Question 1
Let S be the set of all sequences of length 5 whose elements are letters of the English alphabet.
|
(a) How many sequences does S contain?
|
[3 marks]
|
|
(b) How many sequences from S consist of letters that are all different?
|
[3 marks]
|
|
(c) How many sequences from S do not start with A and end with B?
|
[3 marks]
|
[question 1 total: 9 marks]
Question 2
Consider distributing 28 identical balls into 8 distinct boxes numbered 1, . . . , 8.
(a) In how many ways can this be done? [3 marks]
(b) What is the number of such distributions in which for every i ∈ {1, 2, 3, 4}, box i receives at least i balls? [3 marks]
(c) What is the number of such distributions in which all boxes receive an even number of balls? [3 marks]
[question 2 total: 9 marks]
Question 3
(a) What is the coefficient of x4y3 when the expression (2x - y)7 is expanded? [3 marks]
(b) What is the coefficient of x4y3 when the expression (x+y +2)9 is expanded? [3 marks]
[question 3 total: 6 marks]
Question 4
An experiment consists of two fair, different coloured dice being rolled (the dice are 6-sided and the sides show numbers 1, . . . , 6). Let A be the event that the two dice are both showing numbers that are greater than 3, and let B be the event that the sum of the numbers shown on the two dice is 8.
(a) What is the probability of A? [3 marks]
(b) What is the probability of B? [3 marks]
(c) What is the probability of A ∩ B? [3 marks]
(d) Are the events A and B independent? (You must justify your answer!) [3 marks]
[question 4 total: 12 marks]
Question 5
(a) Define the following (you may use terms graph, vertex, edge and path without defining them):
• a connected graph;
• a cycle;
• a cut-edge.
[6 marks]
(b) Let G be a connected graph. Prove that an edge e of G is not a cut-edge if and only if it belongs to a cycle.
In your proof you may use the following lemma (that you do not need to prove).
Lemma: Let G be a graph and u and v two vertices of G. There is a path from u to v in G if and only if there is a simple path from u to v in G. [6 marks]
[question 5 total: 12 marks]
[grand total: 48 marks]