COMP151101
Introduction to Discrete Mathematics
Semester 2 2018/2019
Question 1
In a standard deck of cards there are 4 suits: clubs, diamonds, hearts and spades. Each suit contains 13 cards: 2, 3, . . . , 10, J, Q,K, A. So there are 4 · 13 = 52 cards, in the deck. A poker hand is a 5-card subset of the standard deck of cards.
(a) How many diferent poker hands are possible? [3 marks]
(b) How many poker hands contain two clubs, two diamonds and one spade? [3 marks]
(c) How many poker hands contain at least one spade? [3 marks]
[Question 1 Total: 9 marks]
Question 2
Consider distributing 30 identical balls into 10 distinct boxes numbered 1; . . . ; 10.
(a) In how many ways can this be done? [3 marks]
(b) What is the number of such distributions in which odd numbered boxes are nonempty? [3 marks]
(c) What is the number of such distributions in which the number of balls that each box receives is a multiple of 3? (So we are interested in distributions in which for every i ∈ {1; . . . ; 10}, there exists a nonnegative integer ki such that the number of balls that box i receives is 3ki.) [3 marks]
[Question 2 Total: 9 marks]
Question 3
(a) What is the coefficient of x2y3 when the expression (3x - 2y)5 is expanded? [3 marks]
(b) What is the coefficient of x5y3 when the expression (x + y + 2)10 is expanded? [3 marks]
[Question 3 Total: 6 marks]
Question 4
Three coins are tossed: a 5p coin, a 10p coin and a 20p coin. Let A be the event that an odd number of tails appear. Let B be the event that at least two heads appear.
(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:
• a path of length n (where n is a nonnegative integer);
• a cycle;
• a simple cycle. [6 marks]
(b) Prove that every odd closed path C contains an odd simple cycle. (Hint: use induction on the length l of C.) [6 marks]
[Question 5 Total: 12 marks]
[Grand Total: 48 marks]