School of Mathematics and Statistics
MAST30012 Discrete Mathematics 2021
Assignment 1
Due 23:59pm Monday 6 September 2021
Student Name Student Number
Tutor’s Name Practice Class Day/Time
Submit your assignment online in Canvas LMS.
Please attach this cover sheet to your assignment or use a blank sheet of
paper as the first page of your assignment with Student Name, Student
Number, Tutor’s Name, Practice Class Day/Time clearly stated. .
? Late submission will not be accepted unless accompanied by a medical certificate
(or a similar special consideration). If there are extenuating circumstances you
need to contact your lecturer, preferably prior to the submission deadline. Medical
certificates are usually required.
? Information on how to submit assignments can be found in the Canvas LMS.
? Full working must be shown in your solutions.
? Marks will be deducted for incomplete working, insufficient justification or incorrect
notation.
? Unless otherwise stated, proofs of identities etc. must use combinatorial arguments.
? There are 4 problems (on two pages) each worth 10 marks.
Q1: (a) How many ways are there to give 5 apples and 7 bananas to 12 people assuming
that each person gets a piece of fruit.
(b) How many ways can 7 oranges, 4 pears and 5 bananas be distributed to 16
people if each person gets one piece of fruit?
(c) How many ways are there of distributing 6 apples and 12 oranges to 20 people
with no restriction on the number of apples or oranges a person can get.
(d) You are asked to write down all integers from 1 to 10n, n ∈ N. How many
times did you write down the digit 3.
Q2: In a game of Yatzy players take turns rolling 5 dice. Various combinations earn
points. After a roll, players choose which dice to keep and which to roll again.
Players may roll some or all of the dice up to a total three times on a turn after
which a score (or a zero) is entered into a score box. The game ends when all score
boxes are used. The player with the highest total score wins the game.
Here we consider the simpler version in which players have only one roll
of the 5 dice.
What is the probability of rolling each of the following?
(a) Five of a kind.
(b) A large straight that is 2,3,4,5,6.
(c) A full house which is three of a kind and two of another (such as 5,5,5,2,2).
(d) Three of a kind.
(e) Two of a kind.
Q3: Over a period of m days, in a physical education class of n > 0 students, each day
a student is chosen to lead the class in yoga practice.
(a) How many ways are there of choosing the leaders without any constraints.
(b) How many ways are there of choosing the leaders if a group with k students
are excluded from leading the class.
(c) Let S(m,n) count the number of ways the leaders can be chosen so that every
student gets to lead at least once. Use inclusion-exclusion to prove that
S(m,n) =
n∑
k=0
(?1)k
(
n
k
)
(n? k)m.
Clearly define the sets involved and specify the counting principles you are
using.
(d) Show that S(m,n) = 0, m < n, and S(n, n) = n!.
Q4: Give count-two-ways combinatorial proofs of the following identities. In each case
clearly state the counting problem (subsets, student committees, ice-cream cones or
whatever takes your fancy).
(a) (
33
12
)(
12
6
)(
6
3
)
=
(
33
3
)(
30
3
)(
27
6
)
.
(b) ((
n
k
))
=
n∑
m=0
(
n
m
)((
m
k ?m
))
,
where
((
n
k
))
=
(
n+k?1
k
)
is the number of multisets (or samples with replacement)
of size k from a set with n elements.
(c) (
n + 1
k + 1
)
=
n∑
m=k
(
m
k
)
.