School of Mathematics and Statistics
MAST30012 Discrete Mathematics 2021
Assignment 1 – Solutions
Q1: We first state an equivalent counting problem and then give the answer.
(a) This is equivalent to choosing a subset of size 5 (the people given apples ) from
a set of size 12. The answer is: (
12
5
)
=
12!
7! 5!
.
(b) This is like distributing 16 balls (people) into 3 boxes (oranges, pears and
bananas) with 7 balls in box 1, 4 balls in box 2, and 5 balls in box 3. The
answer is (
16
7, 4, 5
)
=
16!
7! 4! 5!
.
(c) The distribution of each type of fruit (oranges or apples) is independent.
The distribution of a particular type of fruit is the problem of sampling with
replacement (think of people as labelled boxes and fruit as identical balls) so
the oranges can be distributed in:(
20 + 6− 1
6
)
=
(
25
6
)
ways, while the apples can be distributed in(
20 + 12− 1
12
)
=
(
31
12
)
ways. By the multiplication principle the oranges and apples can then be
distributed in (
25
6
)(
31
12
)
ways.
(d) Each integer can be represented as an n-tuple or as a word of length n with
entries from {0, 1, . . . , 9}. In the case n = 3 we would have 7 = (0, 0, 7), 389 =
(3, 8, 9), 1000 = (0, 0, 0) etc. with the entries being the coefficients in the base
10 expansion of the integer. There are 10n tuples and in each position (column)
of the n-tuples there will be 10n−1 occurrences of the digit 3. Since there are
n positions we would write down the digit 3 a total n10n−1 times.
Q2: In each case we make use of the probability axiom. Let T be the set of possible
outcomes and F the set of favourable outcomes. Assuming each outcome is equally
likely, the probability of F is:
Pr(F ) =
number of favourable outcomes
total number of outcomes
=
|F |
|T |
.
Now each roll of five dice can be represented as a five tuple (we distinguish between
the dice) with entries 1, 2, 3, 4, 5 or 6. Hence |T | = 65 = 7776.
(a) Five of a kind can be achieved in 6 ways. Hence
Pr(Five of a kind) =
6
65
=
1
64
≈ 0.0771%.
(b) The required dice values can appear in any order. Hence |F | = 5! is the
number of permutations of 2, 3, 4, 5, 6, and
Pr(A large straight) =
5!
65
≈ 1.543%.
(c) The number of different full-houses is 6× 5 = 30 (6 choices for three of a kind
and 5 for two of a kind). The three dice of the same value can be placed in(
5
3
)
= 10 positions. Hence
Pr(Full-house) =
300
65
≈ 3.858%.
(d) We partition F into 4 cases: Five of a kind, Four of kind and one other, Full-
house, and Three of a kind and two distinct other dice.
Four of kind and one other can occur in 6×5×5 = 150 ways (30 combinations
of dice and 5 configuration in each case).
Three of kind and two distinct other dice can occur in 6× 5× 4×
(
5
3
)
= 1200
ways.
Hence |F | = 6 + 150 + 300 + 1200 = 1656 and
Pr(Three of a kind) =
1656
65
≈ 21.296%.
(e) The only way two of a kind cannot occur is that all dice show distinct values.
This can happen in (6)5 = 6! ways. So |F | = 65−6! = 7056 by the complement
principle and hence
Pr(Two of a kind) =
7056
65
≈ 90.74%.
Alternative Solution: Two of a kind obviously appear in any configuration
with three of a kind. There are two further cases two pairs and a distinct third
(as in 22445) or two of a kind and three distinct others as in (55136).
Two pairs and a distinct third: 6× 5× 4/2 possible combinations (divide by 2
to avoid counting combinations of pairs twice) and for each combination
(
5
2
)(
3
2
)
configurations. In total there are 1800 possibilities.
Two of a kind and three distinct others: 6×5×4×3 possible combinations and
for each combination
(
5
2
)
configurations (note configurations of the distinct 3
are already counted via the combinations). In total there are 3600 possibilities.
Adding it all up we get 1656 + 1800 + 3600 = 7056 as before.
Note that had we not already done the hard work with three of a kind the
complement way is so much easier.
Q3: A configuration of leaders is an m-tuple with n possible distinct ‘values’ (students)
per entry.
(a) With no constraint there are nm ways of choosing the leaders.
(b) There are (n−k)m ways of choosing the leaders if a group a size k are excluded
from leading.
(c) Let L = {1, 2, . . . , n} denote the set of possible leaders and Lj = L\{j} the set
of leaders with student j excluded. The set of configurations in which every
student gets to lead at least once is the complement of Lm with
⋃n
j=1 L
m
j since
Lmj is the set of configurations where student j never gets to lead on any of the
m days. So
S(m,n) = |Lm| −
∣∣∣∣∣
n⋃
j=1
Lmj
∣∣∣∣∣
Use the inclusion-exclusion theorem
= nm −
n∑
k=1
(−1)k−1
∑
{s1,…,sk}⊂{1,2,…,n}
|Lms1 ∩ L
m
s2
∩ · · · ∩ Lmsk |
Lms1 ∩ L
m
s2
∩ · · · ∩ Lmsk is a set with k students s1, s2, . . . , sk excluded so
|Lms1 ∩ L
m
s2
∩ · · · ∩ Lmsk | = (n− k)
m and there are
(
n
k
)
such subsets.
= nm −
n∑
k=1
(−1)k−1
(
n
k
)
(n− k)m
=
n∑
k=0
(−1)k
(
n
k
)
(n− k)m.
(d) You didn’t try to show this using the formula, did you? Combinatorially, this
is easy!
If there are fewer days than students, then clearly it is impossible to have a
configuration in which every students leads at least once. Hence S(m,n) =
0, m < n.
When m = n there are n days and n students. Every permutation of the
students is a valid configuration and hence S(n, n) = n!.
Note: This is a famous result since S(m,n) counts the number of onto functions from
a set of size m to a set of size n.
Q4: (a) Given a group of 33 students choose a committee of size 12 with a subcommittee
of size 6 and from these six an executive committee of size 3.
LHS: Choose the 12 students for the committee in
(
33
12
)
ways. From the com-
mittee of 12 choose a subcommittee of size 6 in
(
12
6
)
, and finally choose the
executive committee of size 3 in
(
6
3
)
ways. The choices at each step are inde-
pendent and the result follows.
RHS: Choose the executive committee of size 3 from all students in
(
33
3
)
ways.
Then choose the remaining 3 members of the subcommittee from the remaining
30 students in
(
30
3
)
ways. Finally, choose the remaining 6 members of the
committee in
(
27
6
)
ways.
Note how you can now derive endless lists of binomial identities such as in this
case (
33
12
)(
12
6
)(
6
3
)
=
(
33
6
)(
27
6
)(
6
3
)
=
(
33
9
)(
9
3
)(
24
3
)
= · · ·
(b) This is a generalisation of the ‘Vandermonde at the ice cream parlour’ example
from lectures.
An ice cream parlour serves n flavours. How many different ice cream platters
are there with k scoops of ice cream.
LHS:
((
n
k
))
by definition using sampling with replacement or multi-choice.
RHS: We partition on the number m ≤ k of distinct flavours. The m flavours
can be chosen in
(
n
m
)
ways and we take one scoop of each. Then we multi-
choose the remaining k −m scoops from the m flavours in
((
m
k−m
))
ways. We
then sum over the number of chosen flavours while appealing to the addition
and multiplication principles.
Alternatively:
Distribute k oranges to n children with no constraint on how many oranges a
child may get.
LHS:
((
n
k
))
by definition.
RHS: Condition on the number, m, of children who gets at least one orange.
We choose m children in
(
n
m
)
ways and give each child an orange. Next dis-
tribute the remaining k −m oranges among the m children in any way. Sum
over the number of chosen children.
(c) Choose subsets of size k + 1 from the set {1, 2, . . . , n, n + 1}.
LHS: By definition,
(
n+1
k+1
)
is the number of subsets.
RHS: Condition on the largest number m + 1 in the subset. The remaining k
elements can be chosen in
(
m
k
)
ways from {1, 2, . . . ,m}. Now m + 1 can range
from k + 1 to n + 1 and the result follows by the addition principle.