The University of Sydney
School of Mathematics and Statistics
Solutions to Tutorial 1 (Week 2)
MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022
1. Given a set X and a subset A ⊆ X , define a function fA : X → {0, 1} by setting
fA(x) = 1 if x ∈ A and fA(x) = 0 if x /∈ A. If B is also a subset of X , define
(fAfB)(x) = fA(x)fB(x).
(a) Work out fAfB when X = {1, 2, 3, 4, 5}, A = {2, 4, 5} and B = {1, 2, 5}.
Solution: fAfB takes that value 1 on 2 and 5 and is 0 elsewhere.
(b) What subset, if any, does fAfB correspond to?
Solution: fAfB corresponds to A ∩ B.
(c) Define f ′A by f
′
A(x) = 1 − fA(x). What subset, if any, does f
′
A correspond
to?
Solution: f ′A corresponds to X \ A.
(d) Form combinations of fA and fB which represent
(i) the union of A and B;
Solution: We have fA∪B(x) = fA(x) + fB(x)− fA(x)fB(x).
(ii) the symmetric difference A+B = (A \B) ∪ (B \ A) of A and B.
Solution: Define (fA + fB)(x) = fA(x) + fB(x) − 2fA(x)fB(x).
Alternatively, define (fA + fB)(x) = fA(x) + fB(x), where addition is
taken modulo 2.
2. For the following sets X , Y and function X → Y , determine whether the function
is injective or surjective
(a) X = N, Y = N, f(x) = x+ 1.
Solution: If x, y ∈ N and x + 1 = f(x) = f(y) = y + 1, then x = y.
Therefore f is injective. Recall that N = {0, 1, 2, . . .}. The function is not
surjective because x+ 1 = 0 has no solution with x ∈ N.
(b) X = Z, Y = Z, g(x) = x+ 1.
Solution: The function g : Z → Z, x '→ x + 1 is injective for the same
reason as in part (a). It is surjective because if x ∈ Z, x = (x − 1) + 1 =
g(x− 1).
(c) X = Z, Y = Z, h(x) = x2 + 5.
Solution: We show that the function h : Z → Z, x '→ x2 + 5 is neither
injective nor surjective. We have f(1) = 12 + 5 = 6 = (−1)2 + 5 = f(−1).
Furthermore, f(x) = x2+5 = 4 is insoluble because the square of an integer
is never negative.
(d) X = Z, Y = Z, p(x) = x3 + 1.
Solution: We show that the function p : Z→ Z, x '→ x3 + 1 is injective
but not surjective. First we prove that p is injective by establishing the
Copyright c© 2022 The University of Sydney 1

stronger result that p is increasing, that is, if x, y ∈ Z and x < y, then
p(x) < p(y). This follows from the fact the function of real variable f(x) =
x3 + 1 is increasing. Finally we show that p is not surjective. If n ! 2,
p(n) ! p(2) = 9. On the other hand if n " 1, p(n) " p(1) = 2. Therefore
p(n) )= 3 for any integer n.
(e) X is a nonempty set, Y = P(X) (the set of all subsets of X), h(x) = {x}.
Solution: The function h : X → P(X), x '→ {x} is injective because if
{x} = h(x) = h(y) = {y}, then x = y. However h is not surjective because
the empty set ∅ ∈ P(X) does not satisfy h(x) = {x} = ∅ for any x ∈ X .
*3. Given finite sets A and B, let E be a subset of A× B. For a ∈ A, let
E(a) = { b ∈ B | (a, b) ∈ E }
and for b ∈ B, let
E∨(b) = { a ∈ A | (a, b) ∈ E }.
Prove that ∑
a∈A
|E(a)| =
∑
b∈B
|E∨(b)|.
Solution: Find the cardinality |E|. For each a ∈ A there are |E(a)| pairs
(a, y) ∈ E and so |E| =
∑
a∈A
|E(a)|. Similarly, for each b ∈ B there are |E∨(b)|
pairs (x, b) ∈ E and therefore |E| =
∑
b∈B
|E∨(b)|. Equating these two expressions
for |E| gives the result.
4. If there are 40 students in the class, their surnames can’t all start with different
letters (because there are only 26 letters). What can be said if there are 80 students
in the class?
Solution: The Pigeonhole Principle says that there must be ,8026- = 4 students
whose surnames begin with the same letter. This doesn’t mean that there is nec-
essarily a letter which ‘has’ exactly 4 students, but there must be a letter which
has at least 4. Recall the reasoning: if each of the 26 letters were to have at most
3 students, then there could be at most 26× 3 = 78 students.
5. How many six-digit numbers are there (not starting with 0)? How many of these
have six different digits? Explain your answers.
Solution: The six-digit numbers are all the numbers greater than or equal to
100000 and less than 1000000, so there are 900000 of them. Another way to count
them is to note that there are 9 possibilities for the first digit, and then choosing
the other digits is an ordered selection of 5 from 10 possibilities with repetition
allowed, so the total is 9 × 105. The number of six-digit numbers which have no
repeated digits is 9 × 9(5) = 9 × 9 × 8 × 7 × 6 × 5 = 136080, because there are 9
choices for the first digit, and then choosing the other digits is an ordered selection
of 5 from 9 possibilities with repetition not allowed.
6. A permutation of {1, 2, 3, 4, 5} can be thought of as a number with these five digits
in some order, such as 21453 or 41352. There are 5! = 120 such numbers.
2
(a) How many of these numbers start with 5 and end with 2?
Solution: To specify such a number we just need to specify the order of
1, 3, 4 in the middle three digits; there are 3! = 6 possible orders.
(b) How many have a first digit which is larger than the second digit?
Solution: The smart answer is that the first digit is just as likely to be
larger than the second digit as it is to be smaller (and they can’t be equal),
so exactly half of the 120 numbers have the required property. Another way
to get the answer 60 is to note that there are ten possibilities for the first
two digits (21, 31, 32, 41, 42, 43, 51, 52, 53, or 54), and for each of these
there are six possibilities for the last three digits, as in the previous part.
(c) How many have the property that the first digit is larger than the second,
which is smaller than the third, which is larger than the fourth, which is
smaller than the fifth? (Hint : what positions can the digit 1 occupy in such
a number?)
Solution: Clearly the digit 1 must be in either second place or fourth
place, because otherwise it would have to be larger than some other digit.
Because the condition is symmetric, the numbers satisfying the condition
where 1 is the fourth digit are just the reversals of the numbers satisfying
the condition where 1 is the second digit. So we only need to consider one of
these cases: say that 1 is the second digit. Then the requirements that the
first digit is larger than the second, and the second smaller than the third,
are automatically satisfied. There are four possible choices for the first digit.
Whatever first digit is chosen, there are three out of {2, 3, 4, 5} remaining to
fill the last three digits, and the requirements mean that we have to choose
the smallest of these three as the fourth digit; the other two can be the third
and fifth digits in either order. So there are 4×2 = 8 numbers satisfying the
condition where 1 is the second digit, and another 8 where 1 is the fourth
digit, so 8 + 8 = 16 is the answer to the question.
*7. Use the Pigeonhole Principle to prove that for any positive integer n, there is
a multiple of n which has no digits other than 0’s and 1’s (in its usual decimal
expression).
Solution: Consider the set of numbers X = {1, 11, 111, 1111, · · · , 111 · · ·1},
where the last number is a string of n ones. If any of the elements of X is a
multiple of n, then we are done, so suppose none of them is a multiple of n. We
then have a function from X to the set {1, 2, · · · , n − 1}, given by taking the
remainder after division by n. By the Pigeonhole Principle, this function cannot
be injective, since |X| > |{1, 2, · · · , n − 1}|. So there must be two elements of X
which have the same remainder after division by n. Subtracting the smaller from
the larger gives a multiple of n which has the form 11 · · ·100 · · ·0, so we are done.
3
The University of Sydney
School of Mathematics and Statistics
Solutions to Tutorial 2 (Week 3)
MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022
1. Suppose you have 7 different ornaments to put on your mantelpiece.
(a) If you want to use all of them, how many possible arrangements are there?
Solution: There are 7 choices for which ornament goes first, then 6 choices
for which goes next, then 5, etc. So the answer is 7! = 5040.
(b) If you want to use 6 of them, how many possible arrangements are there?
Solution: By the same reasoning as in the previous part, the answer is
7 × 6 × 5 × 4 × 3 × 2, which is also 5040. It makes sense that the answer
should be the same as the previous part, because you can imagine storing
the unused ornament at the right-hand edge of the mantelpiece and thus
‘using’ it after all.
(c) If you can use all, some, or none of them, how many possible arrangements
are there?
Solution: If you use k of the ornaments, then by the same reasoning as in
the previous parts, the number of possible arrangements is 7(k) =
7!
(7−k)! . So
the answer is
7!
0!
+
7!
1!
+
7!
2!
+
7!
3!
+
7!
4!
+
7!
5!
+
7!
6!
+
7!
7!
= 13700.
*(d) Divide your answer to part (c) by your answer to part (a); this ratio measures
how much extra freedom you get by not necessarily using all the ornaments.
Notice that it agrees with e up to four decimal places. Is this a coincidence?
Solution: The ratio is 137005040 = 2.718253 · · · , whereas e = 2.718281 · · · .
This is no coincidence, because the ratio can also be written as
1
0!
+
1
1!
+
1
2!
+
1
3!
+
1
4!
+
1
5!
+
1
6!
+
1
7!
,
i.e. the sum of the first eight terms of the series
∞∑
n=0
1
n!
, which is well known
to converge to e.
2. An ordinary knock-out singles tennis tournament (with no seeds or byes) consists
of a series of rounds. In each round, the remaining players play against each other
in pairs, with the losers being eliminated and the winners going through to the next
round; in the last round, the only two remaining players play the final match to
determine the winner of the tournament. Suppose that there are 7 rounds.
(a) How many players are there at the start of the tournament?
Solution: Every round halves the number of remaining players. So if you
imagine starting at the end with the sole winner and going back in time, the
number of players is multiplied by 2 for every round, and there must have
been 27 = 128 players at the start.
Copyright c© 2022 The University of Sydney 1
(b) How many matches are played in total?
Solution: The smart answer is that every match eliminates one player, and
all but one of the original players gets eliminated, so there are 127 matches.
An alternative method is to note that there are 26 = 64 matches in the first
round, 25 = 32 matches in the second, and so on up to 20 = 1 match in the
last round (the final), so the answer is 26+25+ · · ·+20, which equals 27− 1
by the formula for the sum of a geometric progression.
(c) Before the tournament starts, the organizers need to construct the draw,
which specifies who plays who in the first round, and then which first-round
winners play which other first-round winners in the second round, and so on.
Of course, the organizers don’t know who the first-round winners will be, so
in the draw they are just thought of as “the winner of the match between
player X and player Y”, and so forth. How many possible draws are there?
Use the fact, proved in lectures, that the number of ways to group 2k people
into k pairs is
(2k)!
2kk!
. (The answer is too large to evaluate, so just leave it as
a fraction of expressions involving a factorial.)
Solution: Since there are 128 players at the start, the number of possi-
bilities for who plays who in the first round is
128!
264 64!
. Then there are 64
players to be paired off in the second round (their actual identities may not
be known, but they can be identified by what first-round match they won);
the number of ways to do this is
64!
232 32!
, and so forth. In the final round
there are only two players, and only
2!
211!
= 1 way to pair them off, obviously.
By the Product Principle, the total number of draws is the product of all
these numbers, which is
128! 64! 32! 16! 8! 4! 2!
264+32+16+8+4+2+1 64! 32! 16! 8! 4! 2! 1!
=
128!
2127
.
(d) Suppose that after the tournament is finished, the only things that are
recorded are the draw and the winners of each match. How many differ-
ent such records are possible?
Solution: Given the draw, the number of possible outcomes of the tour-
nament is 2127, because each of the 127 matches can have 2 possible winners.
So by the answer to the previous part, the number of possible records is
128!
2127
2127 = 128!. This answer is of course the same as the number of ways
of ordering the 128 players. The explanation for this is that you can use
the record of the tournament to number the players, as follows. The winner
of the final is player 1, and the loser of the final is player 2. The other
semi-finalists are numbered 3 and 4, with player 3 being the one who lost
to player 1 and player 4 being the one who lost to player 2. Then the other
quarter-finalists are numbered 5 up to 8, with player n+4 being the one who
lost to player n for 1 ! n ! 4; and so on until all the players are numbered.
This gives a bijection between the possible records and the numberings of
the players. So the fact that there are 128! possible records also follows from
the Bijection Principle.
2
3. Let X = {m,m+ 1, · · · , n− 1, n} be a set of consecutive positive integers, and A
the subset of X consisting of those elements which are multiples of 3. You would
expect |A| to be about |X|3 , but the latter is not always an integer, so you may have
to round it up or down.
(a) Give an example where |A| does not equal $ |X|3 %.
Solution: One example is X = {3, 4, 5, 6}, where A = {3, 6}. Here
$ |X|3 % = $
4
3% = 1, whereas |A| = 2.
(b) Show that if X = {1, 2, · · · , n}, then |A| = $n3 %.
Solution: If a is a positive integer, then 3a ! n if and only if a ! $n3 %. So
A = {3× 1, 3× 2, · · · , 3× $n3 %}, and the result follows.
(c) Hence give a formula for A when X = {m,m + 1, · · · , n} and m " 2.
Solution: Let Y = {1, 2, · · · , m−1} and Z = {1, 2, · · · , n}, and let B and
C be the subsets of Y and Z respectively consisting of multiples of 3. Then
X is the complement of Y in Z, and A is the complement of B in C. Hence
by the Difference Principle,
|A| = |C|− |B| =
⌊n
3
⌋
−
⌊
m− 1
3
⌋
.
*4. If m is a positive integer, write v2(m) for the exponent of the highest power of 2
that divides m. For example:
v2(m) = 0⇐⇒ m is odd,
v2(m) = 1⇐⇒ m is even but not a multiple of 4,
v2(m) = 2⇐⇒ m is a multiple of 4 but not of 8, etc.
(a) Show that v2(mm′) = v2(m) + v2(m′) for all integers m,m′.
Solution: We can write m = 2v2(m)m0 and m′ = 2v2(m
′)m′0 where m0 and
m′0 are odd. So mm
′ = 2v2(m)+v2(m
′)m0m
′
0 where m0m
′
0 is odd, which shows
that v2(mm′) = v2(m) + v2(m′).
(b) Prove that for all positive integers n,
v2(n!) =
⌊n
2
⌋
+
⌊ n
22
⌋
+
⌊ n
23
⌋
+
⌊ n
24
⌋
+ · · · · · · .
(Note that although this sum appears to go on forever, all the terms will be
zero from a certain point on, because when 2k > n we have $ n2k % = 0.)
Solution: By definition, n! is the product of the numbers 1, 2, 3, · · · , n. So
by the previous part, v2(n!) = v2(1) + v2(2) + · · ·+ v2(n). Now imagine the
numbers 1, 2, · · · , n as positions in a line, with a stack of v2(i) blocks put at
position i. We want to count the total number of blocks; we can do this by
adding up the number of blocks in the bottom level, the number of blocks
in the second level, and so on (once the level is sufficiently high, there will
be no more blocks). The number of blocks in the kth level from the bottom
is the number of elements i ∈ {1, 2, · · · , n} such that v2(i) " k, which by
definition is the number of multiples of 2k in {1, 2, · · · , n}. So there are $ n2k %
blocks in the kth level, and adding up the levels gives the claimed formula.
3
(c) Deduce that v2((2n)!) = n+ v2(n!). How could this be proved another way?
Solution: By the previous part with n replaced by 2n,
v2((2n)!) =
⌊
2n
2
⌋
+
⌊
2n
22
⌋
+
⌊
2n
23
⌋
+
⌊
2n
24
⌋
+ · · ·
= n+
⌊n
2
⌋
+
⌊ n
22
⌋
+
⌊ n
23
⌋
+ · · ·
= n+ v2(n!).
Another proof of this fact comes from the observation made in lectures that
(2n)! = 2nn!(2n − 1)!!, where (2n − 1)!! is the product of the odd integers
from 1 up to 2n− 1. Since (2n− 1)!! is odd,
v2(2
nn!(2n− 1)!!) = v2(2
n) + v2(n!) + v2((2n− 1)!!) = n + v2(n!) + 0,
as required.
*5. Let Fn be the set of functions f : {1, 2, . . . , n} → {1, 2, . . . , n} such that if i < j
then f(i) ! f(j), and for all i, f(i) ! i. Given two rows of boxes with n boxes in
each row,
. . .
. . .
a standard tableau is obtained by placing the numbers 1, 2, . . . , 2n bijectively in
the boxes so that the numbers increase from left to right in each row and so that
each number in the bottom row is larger than the number in the box above it. Let
Tn be the set of standard tableaux with entries 1, 2, . . . , 2n. Construct a bijection
Fn → Tn. [The cardinality |Fn| = |Tn| is known as the n-th Catalan number ].
Solution: Wemay represent a function by the list of its values: f(1)f(2) . . . f(n).
Begin with an increasing function f as described and then create a two-rowed
tableau with first row
f(1), f(2) + 1, f(3) + 2, . . . , f(n) + n− 1
and whose second row consists of the remaining integers from {1, 2, . . . , 2n} in
ascending order.
For i < j we have f(i) ! f(j) and therefore f(i) + i − 1 < f(j) + j − 1. Thus
the first row begins with 1 and is strictly increasing. Moreover, f(n) + n− 1 < 2n
and therefore the last entry in the bottom row is 2n. We need to see that the
values increase down the columns. We can think of filling the tableau beginning
at the leftmost column and proceeding to the right. When we come to fill the k-th
column, the top row will be the one obtained by restricting f to {1, 2, . . . , k} and
so the k-th entry in the bottom row must be at least 2k.
Conversely, if we begin with a standard tableau with two rows of length n, we
construct the increasing function from the first row of the tableau by subtracting
k − 1 from the value in the k-th box for k = 1, . . . , n. The value in the top box of
the k-th row is always less than 2k; that is, f(k) + k − 1 < 2k and so f(k) ! k, as
required.
4
**6. Use the Pigeonhole Principle to prove that for any odd integer m " 3, at least one
of the numbers 22 − 1, 23 − 1, · · · , 2m−1 − 1 is divisible by m.
Solution: Let X = {1, 2, · · · , m− 1}, and let f : X → X be the function which
takes n to the remainder after dividing 2n by m (it is impossible for this remainder
to be 0, since no odd number greater than 1 can exactly divide a power of 2).
Suppose that f(n) = 1 for some n ∈ X : then 2n − 1 is divisible by m, and we
clearly cannot have n = 1, so the desired result follows. Henceforth we assume that
f(n) *= 1 for all n ∈ X , and try to find a contradiction. Our assumption means
that the range of f is a subset of Y = {2, · · · , m−1}, whose size is strictly smaller
than |X|. By the Pigeonhole Principle, f : X → Y cannot be injective, so there
must be two different elements n1 < n2 in X such that f(n1) = f(n2). This means
that 2n1 and 2n2 have the same remainder after division by m, so their difference
2n2 − 2n1 = 2n1(2n2−n1 − 1) has remainder 0, i.e. is divisible by m. Since m is
odd, it must divide the 2n2−n1 − 1 part, which means that 2n2−n1 has remainder 1.
But n2 − n1 is clearly an element of X , and we have shown that f(n2 − n1) = 1,
contradicting our assumption. This finishes the proof.
5
The University of Sydney
School of Mathematics and Statistics
Solutions to Tutorial 3 (Week 4)
MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022
1. A factory makes jelly beans of 15 different flavours, which it sells in bags of 10. If
the jelly beans in a bag must all have different flavours, how many possible kinds
of bag are there? What about if this restriction is removed?
Solution: We are making an unordered selection of 10 from 15 possibilities. If
repetition is not allowed (i.e. you can’t repeat a flavour), the answer is
(
15
10
)
= 3003.
If repetition is allowed, the answer is
(
15+10−1
10
)
= 1961256.
2. If there are 10 chairs in a row and 8 students who want to sit down, you would
normally say there are 10(8) = 1814400 possible outcomes (a case of ordered selec-
tion with repetition not allowed). What unusual circumstances would make you
change this answer to 108? How about
(
10
8
)
or
(
17
8
)
?
Solution: The answer would be 108 if repetition was allowed; in the context
of the question, this would mean that more than one student was allowed to sit
in a single chair (in fact, for the answer to be truly 108, you would even have to
allow the possibility that all the students sit in the same chair). The answer would
be
(
10
8
)
if repetition was not allowed, but the students were indistinguishable in
the sense that it didn’t matter which student sat where – in this case, it is an
unordered selection, and you are really just choosing which 8 of the 10 chairs are
occupied. The answer would be
(
10+8−1
8
)
=
(
17
8
)
if repetition was allowed and it
was an unordered selection – in other words, if more than one student per chair
was allowed, and the students were indistinguishable – in which case you are really
just choosing how many students are sitting on each chair, with a fixed total of 8.
3. Suppose that A and B are subsets of some set X , and |A| = 140, |B| = 92.
(a) Find |A ∪ B|, given that |A ∩ B| = 36.
Solution: By the Inclusion/Exclusion Principle, we have
|A ∪B| = |A|+ |B|− |A ∩ B| = 140 + 92− 36 = 196.
(b) Find |A ∩ B|, given that |A ∪ B| = 150.
Solution: By the Inclusion/Exclusion Principle, we have
|A ∩B| = |A|+ |B|− |A ∪ B| = 140 + 92− 150 = 82.
*(c) Prove that it is impossible to have another subset C of X such that
|C| = 58, |A ∩ B| = 32, |A ∩ B ∩ C| = 10, |A ∪ B ∪ C| = 250.
Copyright c© 2022 The University of Sydney 1
Solution: Suppose there exists a C with these properties. Then by the
Inclusion/Exclusion Principle, we have
250 = |A ∪ B ∪ C|
= |A|+ |B|+ |C|− |A ∩B|− |A ∩ C|− |B ∩ C|+ |A ∩B ∩ C|
= 140 + 92 + 58− 32− |A ∩ C|− |B ∩ C|+ 10
= 268− |A ∩ C|− |B ∩ C|
But both A∩C and B∩C contain A∩B ∩C, so |A∩C| ≥ 10, |B∩C| ≥ 10.
Thus
250 ≤ 268− 10− 10 = 248,
which is a contradiction. Hence no such set C exists.
4. If you are dealt 5 cards from a standard deck of 52 (4 suits, each containing
A,K,Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2), the number of possible hands is
(
52
5
)
= 2598960.
(a) How many of these hands contain the ace of spades?
Solution: If we know that the hand contains the ace of spades, choosing
the rest of it amounts to choosing 4 cards from the other 51. So the answer
is
(
51
4
)
= 249900.
(b) How many of the hands contain exactly two aces?
Solution: There are four aces in the deck, so we can choose the two aces
in
(
4
2
)
= 6 ways. Then we have to choose the remaining 3 cards from the 48
non-aces, which can be done in
(
48
3
)
ways. So the answer is 6
(
48
3
)
= 103776.
(c) How many of the hands contain at least two aces?
Solution: We need to add to the previous answer the number of hands
which contain exactly three aces and the number which contain all four
aces. The number which contain exactly three aces is 4
(
48
2
)
= 4512, and the
number which contain all four aces is
(
48
1
)
= 48, by the same reasoning as in
the previous part. So the answer is 103776+ 4512+ 48 = 108336. Note that
the answer is not
(
4
2
)(
50
3
)
, as you might expect if you thought of choosing
two aces first and then choosing the three other cards. The reason is that
this will count hands which have more than two aces more than once.
(d) How many of the hands are a full house (three of one value and two of
another, with no condition on the suits)?
Solution: We can choose the values involved in 13(2) = 13 × 12 = 156
ways (13 choices for the value which occurs three times and 12 choices for
the value which occurs twice). Then we can choose the suits for the triplet
in
(
4
3
)
= 4 ways and the suits for the pair in
(
4
2
)
= 6 ways. So the answer is
156× 4× 6 = 3744.
(e) How many of the hands are a flush (all of the same suit), but not a straight
flush (all of the same suit and five consecutive values, counting J= 11,
Q= 12, K= 13, A= 14)?
2
Solution: The number of flushes (including straight flushes) is 4×
(
13
5
)
=
5148, because you can choose the suit in 4 ways and then the cards from that
suit in
(
13
5
)
ways. The number of straight flushes is 4× 9 = 36, because once
the suit is chosen you just need to specify the lowest card of the straight,
which can be anything from 2 to 10 (inclusive). So the number of flushes
which are not a straight flush is 5148− 36 = 5112.
*(f) By replacing “at least two” with “at least zero” in part (c), show the equality(
52
5
)
=
(
4
0
)(
48
5
)
+
(
4
1
)(
48
4
)
+
(
4
2
)(
48
3
)
+
(
4
3
)(
48
2
)
+
(
4
4
)(
48
1
)
.
Of what general identity is this a special case?
Solution: Obviously every hand has at least zero aces, so the number
of hands with at least zero aces is
(
52
5
)
. But we could also work it out as
in part (c), by dividing into the cases of no aces, one ace, two aces, three
aces, and four aces, and these would give rise to the terms of the sum on
the right-hand side. This proves the equality. The same argument shows the
general identity: (
n
k
)
=
k∑
k1=0
(
n1
k1
)(
n− n1
k − k1
)
,
for all 0 ≤ n1 ≤ n and k ≥ 0 (notice that some of the terms on the right-hand
side may be zero, if k1 > n1 or k − k1 > n− n1; the argument still works).
5. The 4 players in a bridge game (North, South, East, and West) are each dealt 13
cards from the same deck of 52.
(a) How many possible deals are there (assuming that it matters who gets which
cards)?
Solution: A deal corresponds to a way of writing the set of all 52 cards in
the deck as a disjoint union of four numbered subsets of size 13. These are
counted by the multinomial coefficient(
52
13, 13, 13, 13
)
=
(
52
13
)(
39
13
)(
26
13
)
=
52!
(13!)4
.
*(b) In how many of these deals do North and South end up with all the spades
between them?
Solution: The easiest way to count this is to imagine that you first remove
all the spades from the deck, and then make 3 hands of 13 from the remaining
39 cards, in
(
39
13,13,13
)
ways. The first two of these three hands can then be
given to East and West. The remaining hand can be mixed back with the
spades, and then those 26 cards divided between North and South in
(
26
13,13
)
ways. So the answer is(
39
13, 13, 13
)(
26
13, 13
)
=
39! 26!
(13!)5
.
6. In this question you should use the Stirling numbers S(5, 2) = 15, S(5, 3) = 25,
S(5, 4) = 10 computed in lectures.
3
(a) Count the surjective functions {1, 2, 3, 4, 5}→ {1, 2, 3, 4}.
Solution: By the result proved in lectures, the answer is 4!S(5, 4) =
24× 10 = 240.
(b) Count the ways of assigning five students to five tutors so that exactly one
of the tutors is not assigned any students.
Solution: There are 5 ways to choose which tutor gets no students, and
having made this choice the number of ways is the same as the surjective
functions counted in the previous part. So the answer is 5× 240 = 1200.
(c) Count the ways of assigning five students to four tutors so that at most two
of the tutors are assigned students.
Solution: If the number of tutors who are assigned students is 2, then
there are
(
4
2
)
= 6 ways to choose which two, and then 2! × S(5, 2) = 30
ways to do the assignation. If only one tutor is assigned any students, there
are 4 ways to choose which one, and then the assignation is automatically
determined. So the answer is 6× 30 + 4 = 184.
(d) Write n5 as a linear combination of binomial coefficients
(
n
k
)
.
Solution: Using the formula n5 =
5∑
k=1
k!S(5, k)
(
n
k
)
, we get
n5 =
(
n
1
)
+ 30
(
n
2
)
+ 150
(
n
3
)
+ 240
(
n
4
)
+ 120
(
n
5
)
.
*7. The Bell number B(n) is defined to be the total number of partitions of the set
{1, 2, · · · , n} (or any set with n elements). Thus B(n) =
∑n
k=0 S(n, k). Prove the
following recurrence relation for the Bell numbers:
B(n) =
n∑
i=1
(
n− 1
i− 1
)
B(n− i), for all n ≥ 1.
(Hint: say that the first step in constructing a partition of {1, 2, · · · , n} is to choose
the block containing n.)
Solution: To construct a partition of the set {1, 2, · · · , n}, we can first choose
the block containing n, and then all that remains is to choose a partition of the
complement of that block. The size i of the block containing n can be anything
from 1 to n, and for each specified i the block can be chosen in
(
n−1
i−1
)
ways (since
we know it contains the element n, so we only need to choose i−1 of the remaining
n− 1 elements). The complement then has size n − i, so there are B(n − i) ways
to choose a partition of it. The desired equation follows.
*8. Suppose that m, k ∈ N with m ≥ k. Prove that the number of surjective functions
f : {1, 2, · · · , m}→ {1, 2, · · · , k} equals
∑
m1,m2,··· ,mk≥1
m1+m2+···+mk=m
(
m
m1, m2, · · · , mk
)
.
4
How many terms are there in this sum?
Solution: A surjective function f : {1, 2, · · · , m} → {1, 2, · · · , k} is completely
determined by the preimages f−1(1), f−1(2), · · · , f−1(k), which are all nonempty,
and of which {1, 2, · · · , m} is the disjoint union. If the size of f−1(i) is mi, then
we must have mi ≥ 1 and m1 +m2 + · · ·+mk = m. Having fixed the sizes of the
preimages, the number of ways of choosing them is by definition the multinomial
coefficient
(
m
m1,m2,··· ,mk
)
. So we get the formula in the question. The problem with
this formula is that the number of terms in the sum is too large for it to be of any
practical use. Choosing themi’s is equivalent to choosing the ni’s where ni = mi−1;
these are nonnegative integers which add up to m−k. We saw in lectures that the
number of ways of choosing a k-tuple of nonnegative integers which add up to n is(
n+k−1
k−1
)
, so the number of terms in our sum is
(
m−1
k−1
)
.
**9. Prove the formula
S(n, k) =
1
k!
k∑
i=0
(−1)i
(
k
i
)
(k − i)n
by induction on n, using the recurrence relation for the Stirling numbers.
Solution: When n = 0, the left-hand side is 1 if k = 0 and 0 otherwise. The
right-hand side is
1
k!
k∑
i=0
(−1)i
(
k
i
)
(k − i)0 =
1
k!
k∑
i=0
(−1)i
(
k
i
)
=
1
k!
(1 + (−1))k,
which is obviously also 1 if k = 0 and 0 otherwise. Now assume that n ≥ 1, and
that the formula for S(n− 1, k) holds. The recurrence relation then gives
S(n, k) = S(n− 1, k − 1) + k S(n− 1, k)
=
1
(k − 1)!
k−1∑
i=0
(−1)i
(
k − 1
i
)
(k − i− 1)n−1 +
k
k!
k∑
i=0
(−1)i
(
k
i
)
(k − i)n−1
=
1
(k − 1)!
[
k∑
i=1
(−1)i−1
(
k − 1
i− 1
)
(k − i)n−1 +
k∑
i=0
(−1)i
(
k
i
)
(k − i)n−1
]
=
1
(k − 1)!
k∑
i=0
(−1)i
((
k
i
)
−
(
k − 1
i− 1
))
(k − i)n−1
=
1
(k − 1)!
k∑
i=0
(−1)i
(
k − 1
i
)
(k − i)n−1.
To derive the claimed formula and complete the induction step, we need only use
the fact that
(
k−1
i
)
= k−i
k
(
k
i
)
, which follows easily from the formula
(
n
i
)
=
n(i)
i! . Note
that the result can also be obtained from the Inclusion/Exclusion count of surjective
functions given in lectures, since the number of surjective functions {1, 2, · · · , n}→
{1, 2, · · · , k} is k!S(n, k).
5
The University of Sydney
School of Mathematics and Statistics
Solutions to Tutorial 4 (Week 5)
MATH2069: Discrete Mathematics and Graph Theory Semester 1, 2022
1. Prove by induction that, for all n ≥ 0,
(a) n3 + 5n is a multiple of 3 (i.e. n3 + 5n = 3! for some integer !).
Solution: The n = 0 case holds because 03 + 0 = 0 is a multiple of 3 (it
is 3× 0). Suppose that n ≥ 1 and that the result is known for n− 1, i.e.
(n− 1)3 + 5(n− 1) = 3!, for some integer !.
Then
3! = n3 − 3n2 + 3n− 1 + 5n− 5 = n3 + 5n− 3(n2 − n+ 2) ,
so n3 + 5n = 3(!+ n2 − n + 2) is a multiple of 3, establishing the inductive
step and completing the proof.
(b) 5n − 4n− 1 is a multiple of 16.
Solution: The n = 0 case holds because 50 − 4 × 0 − 1 = 0 is a multiple
of 16. Suppose that n ≥ 1 and that the result is known for n− 1, i.e.
5n−1 − 4(n− 1)− 1 = 16!, for some integer !.
This equation can be rewritten as
5n−1 = 4n− 3 + 16!.
So
5n − 4n− 1 = 5(4n− 3 + 16!)− 4n− 1 = 16(n− 1 + 5!) ,
which is a multiple of 16, establishing the inductive step and completing the
proof.
2. Use the characteristic polynomial to solve the following recurrence relations:
(a) an = 5an−1 − 6an−2 for n ≥ 2, where a0 = 2, a1 = 5.
Solution: The characteristic polynomial is x2 − 5x + 6 = (x − 2)(x − 3)
with roots 2 and 3, so the general solution is an = C12n + C23n for some
constants C1, C2. In our case we have
2 = a0 = C1 + C2 and 5 = a1 = 2C1 + 3C2.
Solving yields C1 = C2 = 1, so the solution is
an = 2
n + 3n.
Copyright c© 2022 The University of Sydney 1
(b) an = 4an−1 − 3an−2 for n ≥ 2, where a0 = −1, a1 = 2.
Solution: The characteristic polynomial is x2 − 4x + 3 = (x − 1)(x − 3)
with roots 1 and 3, so the general solution is an = C11n + C23n for some
constants C1, C2. In our case we have
−1 = a0 = C1 + C2 and 2 = a1 = C1 + 3C2.
Solving yields C1 = −5/2 and C2 = 3/2, so the solution is
an =
3n+1 − 5
2
.
(c) an = 4an−1 − 4an−2 for n ≥ 2, where a0 = 3, a1 = 8.
Solution: The characteristic polynomial is x2 − 4x + 4 = (x − 2)2 with
repeated root 2, so the general solution is an = C12n + C2n2n for some
constants C1, C2. In our case we have
3 = a0 = C1 and 8 = a1 = 2C1 + 2C2,
yielding C1 = 3 and C2 = 1, so the final solution is
an = 3× 2
n + n2n = (n+ 3)2n.
(d) an = 6an−1 − 9an−2 for n ≥ 2, where a0 = 2, a1 = −3.
Solution: The characteristic polynomial is x2 − 6x + 9 = (x − 3)2 with
repeated root 3, so the general solution is an = C13n + C2n3n for some
constants C1, C2. In our case we have
2 = a0 = C1 and − 3 = a1 = 3C1 + 3C2,
yielding C1 = 2 and C2 = −3, so that the final solution is
an = 3
n(2− 3n).
*(e) an = 6an−1 − 11an−2 + 6an−3 for n ≥ 3, where a0 = 3, a1 = 5, a2 = 11.
Solution: The characteristic polynomial is x3−6x2+11x−6 = (x−1)(x−
2)(x− 3) with roots 1, 2, 3, so the general solution is
an = C1 + C22
n + C33
n
for some constants C1, C2, C3. In our case we have
3 = a0 = C1 + C2 +C3, 5 = a1 = C1 + 2C2 + 3C3, 11 = C1 + 4C2 + 9C3,
yielding C1 = 2, C2 = 0 and C3 = 1, so the final solution is
an = 3
n + 2.
2
*(f) an = 6an−1 − 12an−2 + 8an−3 for n ≥ 3, where a0 = 2, a1 = 4, a2 = 16.
Solution: The characteristic polynomial is x3 − 6x2 + 12x− 8 = (x− 2)3
with repeated root 2, so the general solution is
an = C12
n + C2n2
n + C3n
22n
for some constants C1, C2, C3. In our case we have
2 = a0 = C1, 4 = a1 = 2C1 + 2C2 + 2C3, 16 = a2 = 4C1 + 8C2 + 16C3,
yielding C1 = 2, C2 = −1 and C3 = 1, so the final solution is
an = 2
n(2− n+ n2).
3. Companies A and B control the market for a certain product. From one year to
the next, A retains 70% of its custom and loses to B the remaining 30%, while B
retains 60% of its custom and loses to A the remaining 40%. Let an denote the
market share of company A after n years (thus, that of company B is 1−an).
(a) Write down a recurrence relation expressing an in terms of an−1, for n ≥ 1.
Solution: For n ≥ 1, we have
an =
7
10
an−1 +
4
10
(1− an−1) =
3
10
an−1 +
4
10
.
(b) Solve the recurrence relation, in the sense of giving a closed formula for an,
in terms of a0.
Solution: Unravelling the recurrence relation, we get:
an =
3
10
an−1 +
4
10
=
3
10
(
3
10
an−2 +
4
10
)
+
4
10
=
(
3
10
)2
an−2 +
3
10
4
10
+
4
10
=
(
3
10
)2( 3
10
an−3 +
4
10
)
+
3
10
4
10
+
4
10
=
(
3
10
)3
an−3 +
(
3
10
)2 4
10
+
3
10
4
10
+
4
10
...
=
(
3
10
)n
a0 +
4
10
[(
3
10
)n−1
+ · · · +
3
10
+ 1
]
=
(
3
10
)n
a0 +
4
10
(
3
10
)n
− 1
3
10
− 1
=
(
a0 −
4
7
)(
3
10
)n
+
4
7
.
Here the second-last equality uses the formula for the sum of a geometric
progression.
(c) Hence prove that the market share of company A in the long run (i.e. the
limit of an as n→∞) is independent of its initial market share a0.
Solution: As n→∞, the power ( 3
10
)n tends to 0, so an →
4
7
. So whatever
the initial situation, the market tends to a stable situation where company
A has a 4
7
market share and company B has a 3
7
market share.
3
4. Let bn be the number of ways of forming a line of n people distinguished only by
whether they are male (M) or female (F), such that no two males are next to each
other. For example, the possibilities with 3 people are FFF, FFM, FMF, MFF,
and MFM, so b3 = 5. Write down a recurrence relation for bn. Do you recognize
the sequence?
Solution: We have b0 = 1, b1 = 2, and bn = bn−1 + bn−2 if n ≥ 2. To see
this notice that in a line of n people with n ≥ 2, if the last person is female then
there are bn−1 possibilities for the line of the first n − 1 people, whilst if the last
person is male then the second last person must be female, so that there are bn−2
possibilities for the line of the first n − 2 people. We get the Fibonacci sequence
with the first two terms deleted, so bn = Fn+2.
5. Define a sequence recursively by a0 = 1, a1 = 2, and an = an−1an−2 for n ≥ 2.
(a) Find a2, a3, a4, a5 and a6.
Solution: a2 = 2, a3 = 4 = 22, a4 = 8 = 23, a5 = 32 = 25, a6 = 28.
(b) Prove that an = 2Fn, where F0, F1, F2, · · · is the Fibonacci sequence.
Solution: As seen in lectures, we only need to show that 2Fn satisfies the
same initial conditions and recurrence relation as an. The initial conditions
hold because 2F0 = 20 = 1 and 2F1 = 21 = 2. The recurrence relation holds
because for n ≥ 2,
2Fn = 2Fn−1+Fn−2 = 2Fn−12Fn−2,
by the Fibonacci recurrence relation Fn = Fn−1 + Fn−2.
6. Imagine a 2n×2n array of equal-sized squares, where n is some positive integer. We
want to cover this array with non-overlapping L-shaped tiles, each of which exactly
covers three squares (one square and two of the adjacent squares, not opposite to
each other). Since the number of squares is not a multiple of 3, we need to remove
one square before we start. Prove by induction that no matter which square we
remove, the remaining squares can be covered by these L-shaped tiles.
Solution: The base case is clear, because removing a square from a 2× 2 array
leaves 3 squares which can be covered by a single tile. We now prove the claim
for n ≥ 2, assuming its truth for n − 1. Let G be the 2n × 2n array with exactly
one square missing. Denote the quarters of G by UL for upper left, UR for upper
right, LL for lower left and LR for lower right. Each quarter is a 2n−1×2n−1 array,
except that one of the quarters has one square missing. By rotating G if necessary,
we may suppose that the missing square is in LL. Let T be the L-shape formed by
the lower-rightmost subsquare of UL, the lower-leftmost subsquare of UR and the
upper-leftmost subsquare of LR. Then removing T from G produces a union of
four 2n−1×2n−1 arrays each with one square missing, and each of these can be tiled
by L-shapes, by the induction hypothesis. Hence G is tiled by all these L-shapes
together with T , establishing the inductive step and completing the proof.
*7. The following argument ‘proves’ that whenever a group of people is in the same
room, they all have the same height. There must be an invalid step; find it.
4
We argue by induction on the number n of people in the room. The
n = 1 case is obviously true. Suppose that n ≥ 2 and that the claim
holds for rooms with n − 1 people. Let P1, P2, . . . , Pn be the n people
in this room. If Pn were to leave the room we would have a room with
n−1 people, so by the inductive hypothesis, P1, P2, . . . , Pn−1 all have the
same height. We can apply the same reasoning with P1 leaving the room,
so P2, . . . , Pn−1, Pn all have the same height. But P2 is in both these
collections, so all of P1, P2, . . . , Pn have the same height. This establishes
the inductive step, and so the claim holds for all n by induction.
Solution: Since the claim is false even when n = 2, the proof must fail already
in this case; when you run through the argument with n = 2, the error emerges.
The invalid step is the assertion that “P2 is in both these collections”, because this
ignores the convention governing the way these collections were written out. When
you start with n people P1, P2, . . . , Pn and remove Pn, it is reasonable to list the
remaining people as “P1, P2, . . . , Pn−1”, but you have to bear in mind that if n = 2,
this list will just consist of P1 and will not in fact include P2.
*8. For which n is the Fibonacci number Fn even, and for which n is Fn odd? Prove
your answer by induction.
Solution: Examining the first few terms, one is led to guess that Fn is even
when n is a multiple of 3, and odd when n is not a multiple of 3. To prove this
by induction, we first observe that the n = 0 and n = 1 cases are true (because
F0 = 0 is even and F1 = 1 is odd). Then in proving the result for n ≥ 2, we can
assume it for n− 1 and for n− 2. Recall that we have
Fn = Fn−1 + Fn−2.
There are now three cases, depending on the remainder of n after division by 3.
If n ≡ 0 (mod 3) (i.e. n is a multiple of 3), then n− 1 and n− 2 are not multiples
of 3, so Fn−1 and Fn−2 are odd, so Fn is even as required.
If n ≡ 1 (mod 3), then n − 1 is a multiple of 3 but n − 2 is not, so Fn−1 is even
and Fn−2 is odd, so Fn is odd as required.
If n ≡ 2 (mod 3) then n− 1 is not a multiple of 3 but n− 2 is, so Fn−1 is odd and
Fn−2 is even, so Fn is odd as required.
This completes the inductive step, and the claim follows by induction.
**9. Suppose we want to solve a recurrence relation which is almost a kth-order homo-
geneous linear recurrence relation, but with an extra constant term C:
an = r1an−1 + r2an−2 + · · · + rkan−k + C, for all n ≥ k.
Let p(x) = xk−r1xk−1−· · ·−rk be the characteristic polynomial of the homogeneous
recurrence relation obtained by omitting C.
(a) Show that any solution an also satisfies the (k + 1)th-order linear homoge-
neous recurrence relation with characteristic polynomial (x− 1)p(x).
5
Solution: Suppose that the sequence an is a solution of our recurrence
relation. Then for any n ≥ k + 1, we have
an = r1an−1 + r2an−2 + · · · + rkan−k + C and
an−1 = r1an−2 + r2an−3 + · · · + rkan−k−1 + C.
Subtracting the second equation from the first gives
an − an−1 = r1(an−1 − an−2) + r2(an−2 − an−3) + · · · + rk(an−k − an−k−1)
for all n ≥ k + 1, which can be rearranged as
an = (r1 + 1)an−1 + (r2 − r1)an−2 + · · · + (rk − rk−1)an−k + (−rk)an−k−1.
This is the homogeneous recurrence relation with characteristic polynomial
xk+1 − (r1 + 1)x
k − (r2 − r1)x
k−1 − · · ·− (rk − rk−1)x+ rk
= (x− 1)(xk − r1x
k−1 − · · ·− rk−1x− rk) = (x− 1)p(x),
as claimed.
(b) Hence describe the general solution an in terms of the roots of p(x). (The
answer will depend on whether 1 is a root of p(x) or not.)
Solution: Let the different roots of p(x) be λ1, · · · ,λs with multiplicities
m1, · · · , ms (where the multiplicity of a non-repeated root is 1).
First suppose that none of the λi’s equals 1; then (x − 1)p(x) has roots
λ1, · · · ,λs, 1 with multiplicities m1, · · · , ms, 1. By the general solution of
homogeneous recurrence relations given in lectures, (a) implies that
an = (C11 + C12n+ · · · + C1,m1n
m1−1)λn1 + · · ·
+ (Cs1 + Cs2n+ · · · + Cs,msn
ms−1)λns +D,
for some constants Cij, D. Conversely, any sequence an of this form is a solu-
tion of the homogeneous recurrence relation with characteristic polynomial
(x−1)p(x). This is not quite enough to imply that it satisfies our recurrence
relation: but the additional requirement is just the n = k case, namely
ak = r1ak−1 + · · · + rk−1a1 + rka0 + C,
because, as we saw in the previous part, the difference between this equation
and the n = k+1 case is a case of the homogenous recurrence relation, as is
the difference between the n = k+1 case and the n = k+2 case, and so on.
It is easy to see that the n = k case reduces to a constraint on the constant
D, namely
D = r1D + · · · + rkD + C,
so the general solution is given by the above formula but with D specified
to equal
C
1− r1 − · · ·− rk
. (The denominator is p(1), which we assumed to
be nonzero.)
6
Now suppose that 1 is a root of p(x); without loss of generality, λs = 1. Then
(x−1)p(x) has roots λ1, · · · ,λs−1, 1 with multiplicities m1, · · · , ms−1, ms+1.
Solving the homogeneous recurrence, we obtain
an = (C11 + C12n+ · · · + C1,m1n
m1−1)λn1 + · · ·
+ (Cs−1,1 + Cs−1,2n + · · · + Cs−1,ms−1n
ms−1−1)λns−1
+ (Cs1 + Cs2n+ · · · + Cs,msn
ms−1 +Dnms),
for some constants Cij, D. As in the previous case, we have one extra con-
straint on the constant D in order that the n = k case of the desired recur-
rence relation should hold, namely
Dkms = r1D(k − 1)
ms + · · · + rk−1D + C,
so the general solution is given by the above formula but with D specified to
equal
C
kms − r1(k − 1)ms − · · ·− rk−1
. (The denominator is nonzero, because
it is what you get when you substitute x = 1 in the polynomial obtained
from p(x) by applying ms times the operator x
d
dx
; each application reduces
the multiplicity of the root 1 by 1, so it is no longer a root at the end.)
7