The University of Melbourne
School of Mathematics and Statistics
MAST30012
Discrete Mathematics
Semester 2, 2021
Course Guide and Problem Booklet
Lecturer: Professor Sanming Zhou
Office: Room 150, Peter Hall Building
This compilation has been made in accordance with the provisions of Part VB of the copyright act
for the teaching purposes of the University. For the use of students of the University of Melbourne
enrolled in the subject MAST30012.
Contents
Course Information 2
Notes on Logic and Proofs 4
A bit of Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Proof Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Direct Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Contrapositive Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Inductive Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Practice Class Problems 10
Practice Problems on Proofs and Logic . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Practice Class 1: Direct Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Practice Class 2: Arrangements and Combinations . . . . . . . . . . . . . . . . . . . 14
Practice Class 3: Multinomials and Inclusion-Exclusion . . . . . . . . . . . . . . . . . 16
Practice Class 4: Pigeonholes and Ramsey Numbers . . . . . . . . . . . . . . . . . . . 18
Practice Class 5: Parity and Lattice Paths . . . . . . . . . . . . . . . . . . . . . . . . 20
Practice Class 6: Difference Equations and Generating Functions . . . . . . . . . . . 22
Practice Class 7: Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Practice Class 8: Catalan and Functional Equations . . . . . . . . . . . . . . . . . . . 26
Practice Class 9: Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Practice Class 10: Symmetric Group and Applications . . . . . . . . . . . . . . . . . 30
Practice Class 11: Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1
Course Information
Lectures: This course consists of 36 one hour lectures (three per week) and 11 practice classes
(one per week from the second week).
In 2021 this subject is planned to be taught as dual delivery – a combination of on-campus and
online teaching. Lecture capture will be published on the Canvas LMS after each lecture, and
students who are unable to attend lectures in-person are required to watch lecture recordings
in a timely fashion.
In case on-campus teaching is impossible due to COVID-19 related lockdown, lectures and
on-campus practice classes will be switched to online delivery using Zoom.
The lectures are at
• 9:00-10:00 Mondays, Baldwin Spencer Theatre
• 14:15-15-15 Wednesdays, Baldwin Spencer Theatre
• 10:00-11:00 Thursdays, Baldwin Spencer Theatre
Practice classes: Students should attend one of the practice classes which are held weekly.
Practice classes start on Monday in Week 2.
• Zoom: 14:15-15:15 Mondays, 15:15-16:15 Thursdays
• Room 213, Peter Hall Building: 13:00-14:00 Wednesdays, 9:00-10:00 and 11:00-12:00
Thursdays
Assessment: Assessment is based on a 3-hour end-of-semester written exam [X marks out of
80] and three written assignments during semester [A marks out of 20]. The final mark M out
of 100 will be M = X + A.
Subject Web Page: A web page will be maintained for this subject on the LMS. Lecture
notes and supplementary materials will be available from this site.
Subject Overview: Discrete Mathematics is concerned with the study of objects which can
take only distinct values and which depend on a discrete variable such as the size of a finite
set, the number of nodes in a network etc. However, there is no exact definition of “discrete
mathematics” and the term is perhaps best described by what is excluded: continuously varying
quantities and related notions (though even this can and will be relaxed when convenient).
The main topics to be covered in this course are: enumeration, permutations, designs, finite
geometry, words, Ramsey theory and physical combinatorics. Designs are relevant to statis-
tics, Ramsey theory to computer science, and physical combinatorics to mathematical physics.
Words are useful for representing and constructing objects and relating combinatorial objects
to algebraic structures.
Generic Skills: In addition to learning specific skills that will assist students in their future
careers in science, they will have the opportunity to develop generic skills that will assist them
in any future career path. These include:
2
• problem-solving skills: the ability to engage with unfamiliar problems and identify relevant
solution strategies
• analytical skills: the ability to construct and express logical arguments and to work in abstract
or general terms to increase the clarity and efficiency of analysis
• collaborative skills: the ability to work in a team
• time-management skills: the ability to meet regular deadlines while balancing competing
commitments.
3
Notes on Logic and Proofs
A bit of Logic
A statement or proposition P is a declarative sentence that is true or false but not both. If
P is a true statement, then its truth value is true; otherwise its truth value is false. These
can be mathematical statements (such as “2 + 2 = 4”, “15 is a prime”) or non-mathematical
(“Adam is older than Eve”, “Sydney is the capital of Australia”). Sentences such as “What
time is it?” or “Good heavens!” are not propositions. Note that a mathematical expression
such as, x+ y = z, isn’t a statement because it is neither true nor false since the variables have
not been assigned values.
Existing statements can be used to form new statements by use of logical operators called
connectives. We will only look at three basic connectives here. The negation of a statement
P is denoted as ¬P , obviously if P is true then ¬P is false and vice versa. The statement “P
and Q”, denoted as P ∧Q, is called the conjunction of P and Q and is true if both statements
P and Q are true and is false otherwise. Similarly, “P or Q”, denoted as P ∨ Q, is called
the disjunction of P and Q and is false if both P and Q are false and true otherwise. Two
statements constructed from P and Q using connectives are logically equivalent if they they
have the same truth values for all possible truth values of P and Q. As an example we have
¬(P ∨Q) is logically equivalent to (¬P ∧ ¬Q) and
¬(P ∧Q) is logically equivalent to (¬P ∨ ¬Q)
For statements P and Q, the implication P ⇒ Q (often expressed as “If P , then Q.”) is
true except in the case P false and Q true. P ⇒ Q can also expressed as: (1) P implies Q;
(2) P only if Q; (3) P is sufficient for Q; (4) Q is necessary for P . We also say that, P is a
sufficient condition for Q and Q is a necessary condition for P . For statements P and Q,
the converse of the implication P ⇒ Q is the implication Q⇒ P , while the contrapositive
of P ⇒ Q is the implication ¬Q ⇒ ¬P . Note that an implication and it contrapositive are
logically equivalent, however this is not the case for an implication and its converse. We write
P ⇔ Q to mean (P ⇒ Q) ∧ (Q ⇒ P ) and in words we say “P if and only if Q.” or “P is
necessary and sufficient for Q.” For the phrase “if and only if” we often use the short-hand
“iff”.
Example Consider the statement
Let a, b ∈ R. If ab = 0, then a = 0 or b = 0.
The converse statement is
Let a, b ∈ R. If a = 0 or b = 0, then ab = 0.
The contrapositive statement is
Let a, b ∈ R. If a 6= 0 and b 6= 0, then ab 6= 0.
4
Note that the “or” from the original statement becomes “and” in the contrapositive. Finally
we have
Let a, b ∈ R. Then ab = 0 if and only if a = 0 or b = 0.
A declarative sentence containing one of more variables is often referred to as an open sen-
tence. When the variables are assigned values the open sentence becomes a statement whose
truth value can de determined and depends on the values assigned to the variables. Open sen-
tences can also be converted into statements by means of quantifiers, resulting in quantified
statements. Suppose that P (n) is an open sentence expressed in terms of an integer vari-
able n. The universal quantifier, denoted by ∀, represents for all, for each, or for every.
Therefore,
∀n ∈ Z, P (n) : For every integer n, P (n).
is a quantified statement which is true if P (n) is true for every integer n. The existential
quantifier, denoted by ∃, can be expressed in words as there exists, for some or for at
least one. Therefore,
∃n ∈ Z, P (n) : There exists an integer n such that, P (n).
is a quantified statement which is true if P (n) is true for one or more integers n.
Example For an integer variable n,
P (n) : 7n+ 3 is an even integer.
is an open sentence and ∀n ∈ Z, P (n) is a false statement since P (2) is false, while ∃n ∈ Z, P (n)
is a true statement since P (1) is true.
We can negate quantified statements as per
¬(∀n, P (n)) is logically equivalent to ∃n,¬P (n) and
¬(∃n, P (n)) is logically equivalent to ∀n,¬P (n).
With P (n) as in the example above we have
¬(∀n, P (n)) is logically equivalent to ∃n, 7n+ 3 is an odd integer, which is true, and
¬(∃n, P (n)) is logically equivalent to ∀n, 7n+ 3 is an odd integer, which is false.
where we used that the statement “not an even integer” is equivalent to “an odd integer”.
5
Proof Techniques
Most theorems can be put into one of the following two forms, where P and Q are statements.
Theorem A. If P then Q.
Theorem B. P if and only if Q.
To prove Theorem A, you can prove it directly by assuming P and making some deductions
ending with Q. Another very common approach is to assume that Q is false and then by
deduction arrive at a conclusion which is either clearly false or contradicts the assumptions
made in P .
Alternatively we can prove the equivalent form, the contrapositive: “If Q is false then P
is false.” Here “Q is false” means that the negation of Q, that is ¬Q is true. Proving the
contrapositive is very often indistinguishable from proof by contradiction.
The converse of Theorem A is “If Q then P .” This is not equivalent to Theorem A.
Theorem B is equivalent to the statement that Theorem A and its converse are both true. To
prove Theorem B, we break the proof up into two parts: “if P then Q” (or “P implies Q”) and
“if Q then P” (or “Q implies P”).
Direct Proofs
This is a method of proof that gets you from a premise or statement P to another true statement
Q typically by using logical deduction, algebraic manipulation, etc. In the case of a quantified
statement such as ∀n, P (n) ⇒ Q(n) we can prove this by starting with an arbitrary n, for
which P (n) is true, and then show that Q(n) is true.
Example If n is an even integer, then 5n+ 7 is an odd integer.
Proof: Assume that n is an even integer. Then n = 2k for some integer k. Therefore,
5n+ 7 = 5(2k) + 7 = 10k + 7 = 10k + 6 + 1 = 2(5k + 3) + 1.
Since 5k + 3 is an integer, 5n+ 7 is an odd integer.
Counterexample
A mathematical statement that can be expressed as an implication can be shown to be false by
providing a counterexample. So to show that “all elements in a set S have property P” is false,
all we have to do is come up with one element (member) in S that does not have property P .
6
Proof by Contradiction
In a proof by contradiction of some mathematical statement A is true, we assume that A is
false and show that this leads to a contradiction (say we derive an obviously false statement by
logical deduction). Perhaps the most famous proof by contradiction is the following.
Example There are infinitely many primes.
Proof: Assume to the contrary that there is a finite number, say n, of primes and list them
all as p1, p2, . . . , pn. Now form the number
a = 1 + p1p2 · · · pn.
Clearly a is not divisible by any of the primes p1, p2, . . . , pn. Since any integer is either prime
or a product of primes (this statement is proved later) it follows that a is prime. So there is at
least n+ 1 primes. This contradicts our assumption that there is a finite number n of primes.
Example The Pigeonhole Principle Let n be an integer. If (n + 1) (or more) pigeons
occupy n pigeonholes, then at least one pigeonhole house 2 or more pigeons.
Proof: Suppose to the contrary that none of the n pigeonholes contains more than one pigeon.
Then the total number of pigeons would be at most n. This is a contradiction since we assumed
there were at least n+ 1 pigeons.
We next consider the classical proof that
√
2 is irrational. First we need a couple of results.
Lemma 1 The square of an odd number is odd. The square of an even number is even.
Proof: We give a direct algebraic proof of the first statement. Assume that n is odd, then n can
be written in the for n = 2m+1. By algebra, n2 = (2m+1)2 = 4m2+4m+1 = 2(2m2+2m)+1,
which is of the form 2p+ 1 and hence n2 is odd. Similarly we can prove the second statement.
Lemma 2 If n2 is even, then n is even.
Proof (by contradiction): Assume that n is not even. Then n must be odd and by Lemma 1
n2 would be odd. But n2 is even. This is a contradiction, so n must be even.
Theorem 1
√
2 is irrational.
Proof (by contradiction): Assume to the contrary that
√
2 is rational. Then we can find
integers p and q (with no common divisors) so
√
2 = p/q. Since p and q have no common
divisors they cannot both be even. Since
√
2 = p/q we have p2 = 2q2 and p2 is therefore even.
By Lemma 2 p is even. So we may write p = 2r and we thus have (2r)2 = 4r2 = 2q2 from
which we get q2 = 2r2. So q2 and hence q is even. But this is a contradiction since both p and
q can’t be even and we therefore conclude that
√
2 is irrational.
7
Contrapositive Proof
Example The Pigeonhole Principle Let n be an integer. If (n + 1) (or more) pigeons
occupy n pigeonholes, then at least one pigeonhole house 2 or more pigeons.
We first identify the relevant statements. The theorem is of the form “If P then Q”, where
• P : “(n+ 1) (or more) pigeons occupy n pigeonholes.”
• Q: “at least one pigeonhole house 2 or more pigeons.”
We must now prove “If ¬Q then ¬P” where we have
• ¬Q: “every pigeonhole house at most one pigeon.”
• ¬P : “n (or less) pigeons occupy n pigeonholes.”
Now a proof proceeds as the previous proof by contradiction.
Inductive Proof
Induction rests on the following principle: Let P (n) be a statement involving an arbitrary
integer n. Suppose both of the following statements have been proved for some integer n0:
(i) P (n0) is true;
(ii) if P (k) is true for all n0 ≤ k < n, then P (n) is true.
Then it can be concluded that P (n) is true for all integers n ≥ n0.
The statement “P (k) is true for all n0 ≤ k < n” is called the inductive hypothesis.
Note. This is a generalised version of mathematical induction. You may have seen a simpler
version before, where (ii) is “if P (n − 1) is true then so is P (n)”. The generalised version is
often referred to as strong induction. The two versions of induction are logically equivalent.
8
Example: For every positive integer n we have
n∑
m=1
m = n(n+ 1)/2.
Proof: For n = 1 we have LHS =
1∑
m=1
m = 1 and RHS = 1(1 + 1)/2 = 1.
Assume now that the statement is true for n = k − 1. Then
k∑
m=1
m = k +
k−1∑
m=1
m
= k + k(k − 1)/2 by Induction hypothesis
=
2k + k(k − 1)
2
=
k2 + k
2
= k(k + 1)/2.
The statement is thus true for n = k and hence by Mathematical Induction it is true for all n.
Example: Every integer n ≥ 2 is either prime or can be expressed as a product of primes.
Proof: The statement is clearly true for n = 2.
For an arbitrary integer k ≥ 2, assume that every integer m, with 2 ≤ m ≤ k, is either prime
or can be expressed as a product of primes. Now consider the integer k + 1. If k + 1 is prime
then there is nothing further to prove. If k + 1 isn’t prime then it is composite and there exist
integers a and b such that k+1 = ab with 2 ≤ a ≤ k and 2 ≤ b ≤ k. Therefore, by the induction
hypothesis, each of a and b is either prime or can be expressed as a product of primes. In either
case, k + 1 = ab is a product of primes.
9
Problem Booklet
This booklet contains a set of practice class problems covering the material of the course.
The practice class problems are intended as exercises to be worked through during your timetabled
practice class.
Practice class solutions will be handed out in the subsequent practice class. All practice class
solutions will be placed on the subject web site at the end of semester.
10
The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Problems on Proofs and Logic
The logical proposition A ⇒ B means statement A implies statement B.
It is often written: if A, then B.
Q1: (a) The pigeonhole principle states that if n + 1 blocks are placed in n boxes, then at
least one box contains 2 or more blocks. Write this in the form A⇒ B by identifying
statements A and B.
(b) Let f : ∆ → ∆ be a mapping from a triangular shaped region ∆ into the same
region. The Brouwer fixed point theorem states that if f is continuous, then there
exist a fixed point (i.e. a point (x, y) such that f((x, y)) = (x, y)). Write this in the
form A⇒ B by identifying statements A and B.
The converse of the logical proposition A ⇒ B is the logical proposition
B ⇒ A. In the case that the converse is true, one writes A ⇔ B. This is
read A is equivalent to B, or A if and only if B. Sometimes the phrase if
and only if is abbreviated as iff.
Q2: (a) Write down the converse of the following logical proposition: if the rows of a square
matrix are linearly independent, then the matrix is invertible. Is the converse true?
Write down both the proposition and its converse in the one sentence.
(b) Write down the following logical statement as two separate statements:
sinπx = 0 ⇔ x ∈ Z.
The logical proposition A⇒ B is logically equivalent to the logical propo-
sition ¬B ⇒ ¬A, where the symbol ¬ denotes not. This is called the
contrapositive form of the proposition.
Q3: (a) Write down the contrapositive form of the pigeonhole principal as stated in Q1(a).
(b) A variant of the pigeonhole principal states that if two boxes contain a1+a2−1 blocks,
then either box 1 contains at least a1 blocks, or box 2 contains at least a2 blocks.
Write down the contrapositive form of this, and prove the resulting proposition.
(c) Write down the contrapositive form of the proposition: for real numbers x1, . . . , xn,
if x1 + · · · + xn > n(n + 1)/2, then there is a value of i for which xi > i. Prove the
resulting proposition.
11
The method of proof by contradiction for the logical proposition A ⇒ B
involves showing that the statements ¬B and A together are incompatible
in that they lead to a contradiction.
Q4: (a) In the setting of Q1(a), suppose each box contains one or less blocks, and n + 1
blocks are placed in n boxes. Argue that this leads to a contradiction, and hence
prove the pigeonhole principle.
(b) Use a proof by contradiction to prove the pigeonhole principle of Q3(b).
(c) Use a proof by contradiction to prove the pigeonhole principle of Q3(c).
The principle of mathematical induction. Let P (n) be a statement
relating to a positive integer. By showing that
(a) P (1) is true.
(b) For k ≥ 2, P (k) is true, where it is assumed that P (1), . . . , P (k−1) are
all true.
We can conclude that P (n) is true for every positive integer n.
Q5: The objective of this exercise is to use mathematical induction to prove that
n∑
p=1
p =
n(n+ 1)
2
.
(a) Verify that the statement is true for n = 1.
(b) Assume the statement is true for n = 1, 2, . . . , k − 1. The aim now is to verify that
it is then true for n = k. To do this, note that
k∑
p=1
p =
k−1∑
p=1
p+ k.
What can now be concluded?
Q6: The Fibonacci numbers {F1, F2, . . . } are the sequence specified by the recurrence
Fn = Fn−1 + Fn−2, n ≥ 3, with F1 = F2 = 1.
(a) Write out the first six Fibonacci numbers.
(b) Use mathematical induction to prove that
n∑
p=1
(Fp)
2 = FnFn+1.
12
The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 1: Direct Enumeration
There are two primary methods of direct enumeration:
• The Addition Principle, and the
• Multiplication Principle.
There is the also the Complementary Priciple but this is a simple corollary
of the Addition principle and so not often stated.
Q1: Find the number of ordered pairs (x, y) of integer solutions of the inequality x2 + y2 ≤ 5.
Geometrically this is the number of integer coordinate points inside or on the circle.
Q2: Let X = {1, 2, 3 . . . , 100} and let S = {(a, b, c) | a, b, c ∈ X, a < b and a < c}. Find |S|. Q3: Roll two dice. What is the probability that the sum of the number of eyes is even? Q4: A password must consist of upper case letters and digits. How many passwords are there of length 8 containing at least one digit? You may assume we are using the standard English alphabet with 26 characters. Q5: Using the set of letters from the alphabet A = {a, b, c, d, e, f, g} how many words of length five are possible in the following cases: (a) There are no restrictions on how many times a letter may be used. (b) Each letter can be used at most once. (c) Repetition of letters is allowed but no letter may occur next to itself, i.e,. subwords of the form xx, x ∈ A are forbidden. These are known as square free words. (d) Repetition is allowed but the letters must occur in alphabetical order. Q6: A palindrome is a string of characters which reads the same backward or forward. How many bit strings (words in the alphabet {0, 1}) are palindromes? Q7: Nine cars are parked in a row. Four identical cars are painted red and five identical cars are painted blue. How many ways can the cars be parked in a line so that there are never two red cars next to each other? There are at least two ways to solve this problem: a longer ‘by cases’ method and a much quicker method using combinations. 13 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 2: Arrangements and Combinations • An arrangement refers to an ordering of distinct symbols. If there are n distinct symbols, there are n! different arrangements. • A combination of r symbols from n distinct symbols refers to a subset of size r, and thus order does not matter. The number of distinct combinations ( n r ) , pronounced n choose r, is equal to n! r!(n− r)! . • The number of ways to arrange r white blocks and n− r black blocks in a line is ( n r ) . Q1: (a) At an ice cream parlour there are twenty different flavours. How many choices of triple headers are there, assuming each consists of three different flavours. (b) How many ways can a group of 8 people break up into pairs? Answer this question by thinking of the people as standing in a line, and form the pairs from left to right. (c) Answer (b) by first sorting pairs of people into boxes (1),(2),(3),(4), then dividing out by 4! (the number of arrangements of the boxes). (d) Toss a coin 10 times. What is the probability of 5 heads and 5 tails? What is is the probability of (at least) 5 heads in a row? What is is the probability of exactly 5 heads in a row? The number of ways to choose r symbols from n, allowing repetition but not distinguishing different ordering, is(n+ r − 1 r ) . Each choice is a “multiset”. Q2: (a) Illustrate this result by listing all combinations of 3 elements from {a, b} with repe- tition allowed. (b) Use this formula to answer Q1(a) in the case that repetition is allowed. (c) Consider n− 1 symbols I, and r symbols x. How many ways can they be arranged in a line? Interpret the number of x′s between the (j − 1)th I and the jth I as the number of repetitions of xj to deduce the result in the box. (d) From your answer to (c) write down the number of ways to distribute r identical objects to n different people, where repetition is allowed. 14 The symbol ( n r1, r2, . . . , rp ) , known as the multinomial coefficient, stands for the number of ways in which we can put r1 labelled blocks into box B1, r2 labelled blocks into box B2, . . . , rp labelled blocks into box Bp, where r1 + · · ·+ rp = n. We have( n r1, r2, . . . , rp ) = ( n r1 )(n− r1 r2 )(n− r1 − r2 r3 ) · · · (n− r1 − · · · − rp−1 rp ) = n! r1!r2! · · · rp! . Q3: (a) Derive the above formula. (b) Show that ( n r1, n− r1 ) = ( n r1 ) . (c) Show that the multinomial coefficient counts the number of ways of partitioning a set of n symbols into subsets of size r1, . . . , rp. [Hint: Identify the subsets with the boxes.] The binomial coefficients satisfy the recurrence(n r ) = (n− 1 r − 1 ) + (n− 1 r ) . The terms on the right hand side have the combinatorial interpretation as the subsets of size r which contain the element 1, plus those that do not. Q4: (a) By repeated use of this recurrence, show that(n+ r + 1 r ) = (n+ r r ) + (n+ r − 1 r − 1 ) + · · ·+ (n 0 ) . (b) By breaking the subsets of {1, 2, . . . , n + r + 1} of size r into those not containing element 1, those containing element 1 but not element 2, those containing elements 1 and 2, but not element 3 etc., give a combinatorial meaning to the identity in (a). Q5: (a) Show how to associate with a choice of a subset of size r from a set of n elements an ordering of r 1’s and n− r 2’s in a line. Hence deduce the total number of orderings. (b) In Q3(c) label each member of the original set by a 1 if it goes into subset 1, by a 2 if goes into subset 2, . . . by a p if it goes into subset p. Conclude from this that the multinomial coefficient also counts the number of orderings of r1 lots of 1’s, r2 lots of 2’s, . . . rp lots of p’s in a line. 15 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 3: Multinomials and Inclusion-Exclusion • The binomial expansion reads (1 + t)n = n∑ k=0 (n k ) tk. It has the combinatorial interpretation that the t in the jth factor of (1+ t) corresponds to choosing the element j from {1, 2, . . . , n}, so the coefficient of tk gives the number of subsets of size k. • The multinomial coefficient( n k1, k2, . . . , kr ) , with n = k1 + · · ·+ kr, counts the number of ways to partition a set of n elements into r subsets of sizes k1, . . . , kr, or equivalently the number of ways to arrange k1 1’s, k2 2’s, . . . , kr r’s in a line. Q1: (a) How many ways are there to distribute 3 oranges and 4 pears to 7 people so that each person gets one piece of fruit? (b) In (1 + t)n, think of the t in the jth factor of (1 + t) as corresponding to choosing the element j from {1, 2, . . . , n}. How any ways are there to choose k t’s from these factors? Hence deduce the binomial expansion. (c) How many ways are there to give one of 4 twenty cent pieces, 3 ten cent pieces, 1 fifty cent piece and 2 one dollar coins to ten different people? (d) Generalise the reasoning of (b) to deduce the expansion (1 + s+ t)n = ∑ k1,k2≥0 k1+k2≤n ( n k1, k2, n− k1 − k2 ) sk1tk2 . Q2: (a) The formula for the number of ways to choose a subset of size r from a set of n elements, with repetition allowed, is ( n+r−1 r ) . Explain why this same formula gives the number of ways to distribute r identical blocks into n boxes, with repetition allowed. (b) Calculate the number of ways to distribute 4 oranges to 8 people, if there is no restriction on the number of oranges that can go to any one person. 16 The principle of inclusion and exclusion gives the formula |A1 ∪ A2 ∪ · · · ∪ Ar| = |A1|+ |A2|+ · · ·+ |Ar| −|A1 ∩ A2| − |A1 ∩ A3| − · · · |Ar−1 ∩ Ar| +|A1 ∩ A2 ∩ A3|+ · · ·+ |Ar−2 ∩ Ar−1 ∩ Ar| ... +(−1)r−1|A1 ∩ A2 ∩ · · · ∩ Ar| = r∑ k=1 (−1)k−1 ∑ {s1,...,sk}⊂{1,2,...,r} |As1 ∩ As2 ∩ · · · ∩ Ask |. Q3: A group of people can read at least one of the languages Latin, Greek and Russian. Six can read Latin, six Greek and seven Russian. Four can read Latin and Greek, three can read Greek and Russian, two can read Russian and Latin, and one all three languages. (a) How many people are there in the group? (b) Calculate the number of people who read Latin, but do not read Greek or Russian. (c) How many people read Russian only? Q4: The objective of this exercise is to compute the number of ways that 3 distinct pairs of socks can be hung on a single cord clothes line such that there are no 2 socks from the same pair in succession. (a) How many ways can the 3 pairs of socks be arranged on the line without restriction? (b) How many ways are there to arrange the 3 pairs of socks on the line, given that (i) at least one pair is in succession; (iii) at least two pairs are in succession; (ii) all three pairs are in succession? (c) From your answers to (a) and (b), use the inclusion/exclusion principle to answer the original question. Q5: Let Pk, 1 ≤ k ≤ 3 denote the set of all permutations of {1, 2, 3} which leave the position of the number k fixed. (a) Calculate |Pk|, the number of elements in the set Pk. (b) Describe in words the set Pj ∩ Pk for j 6= k, and calculate |Pj ∩ Pk|. (c) Calculate |P1 ∩ P2 ∩ P3|. (d) In terms of the sets Pk, use the inclusion/exclusion principle to write down a formula for N0, the number of permutations of {1, 2, 3} which leave no numbers fixed. From this, and your answers to (a)–(c), show that N0 = 3! ( 1− 1 1! + 1 2! − 1 3! ) (e) Use the above formula to calculate the probability that if 3 identical looking um- brellas are put on an outside rack on a rainy day, none of the 3 owners will reclaim the correct one. 17 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 4: Pigeonholes and Ramsey Numbers • The pigeonhole principle say that if there are n+ 1 blocks in n boxes, at least one box must contain 2 or more blocks. • The generalised pigeonhole principle says that if there are m blocks in n boxes, at least one box must contain at least⌊ m− 1 n ⌋ + 1 blocks. Q1: Starting with January, put months into the same box if their 13th days fall on the same day of the week. Assume it is not a leap year, and label the boxes by 0 to 6, indicating the day of the week, with 0 corresponding to the 13th January. Conclude that there must be at least one, and no more than 3, Friday the 13ths in any one year. Q2: Consider a group of n people, in which all pairs of people are either friends or strangers. Show that there must be two people who are friends with the same number of people. [Hint: Consider separately the case that there is at least one person who is a stranger to all people in the group.] Q3: Consider a circle of unit radius. Show that out of 6 points marked at random (inside but not on the circumference), there must be at least two points within a distance of one unit from each other. [Hint: Divide the circle into 6 equal sectors, and choose one of the boundaries to pass through one of the points.] Q4: Ten players take part in a chess tournament, in which each player plays one game against each other player. A player scores 1 point for a win; −1 for a lose; and 0 for a draw. When the tournament was over, it was found that more than 70% of the games ended in a draw. We want to show that there are two players who have the same total score. (a) How many games were played in total? (b) From your answer to (a), calculate the minimum number of games which ended in a draw, and hence the maximum number of games which did not end in a draw. (c) Put players into one of two pigeonholes according to their final score being positive or negative, and suppose to the contrary of the statement of our objective that all players have different scores. With this assumption, show that there must be at least 5 players with positive scores, or 5 players with negative scores. (d) With at least 5 players having positive (negative) scores which are all different, count up the minimum number of wins (loses) and show that this contradicts (b). Hence conclude that there are two players who have the same score. 18 The Ramsey number R(a, b) is the minimum number of people in a group, in which each person is either a friend or a stranger, it takes to be sure that there will be either a mutual friends, or b mutual strangers. Q5: Write down the meaning of R(a, b) in terms of connecting points with coloured lines. Q6: Six people correspond by SMS with one another — each one with all the rest. Only two topics are discussed — relationship gossip and what’s on next weekend. Use knowledge of Ramsey theory to conclude that at least three people in the group all correspond to each other about the same topic. Q7: The objective of this exercise is to prove that out of any group of 10 people, there is either a set of 3 or more mutual strangers, or 4 or more mutual friends, making use of the generalised pigeonhole principle. (a) Choose a particular person, person 1 say. Put people into pigeonholes according to them being a friend of person 1, or a stranger to person 1. According to the generalised pigeonhole principle, what is the minimum number of people that one of the pigeonholes must contain? (b) Suppose there are 5 or more mutual strangers to person 1. Argue that there must be 4 or more mutual friends, or else a pair of mutual strangers, and hence deduce the result. (c) Show that the result of (b) holds if there are only 4 people which are strangers to person 1. (d) Finally, suppose there are 3 or less strangers to person 1, and thus 6 or more friends of person 1. Use the fact that R(3, 3) = 6 to deduce the sought result. Q8: (a) Specify in words the complete graph K9. (b) How many edges does it have? (c) If each edge can be one of two colours, as in the Ramsey theory interpretation, how many different colourings are there? (d) Why can we be sure that within each of the different colourings there will be either the complete graph K4 in one colour, or the complete graph K3 in the other colour? Would this be true if we started with K8 instead? 19 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 5: Parity and Lattice Paths Consider an interval with the left endpoint labelled by 0, and the right endpoint labelled by 1. If this interval is divided into subintervals, and each subinterval endpoint labelled by 0 or 1, the number of subintervals with a different labelling at each endpoint is odd. Q1: Consider an interval with both endpoints labelled by 0. Suppose this interval is divided into subintervals, and each endpoint labelled by 0 or 1. (a) Regard each 0 as a wall, and each 1 as a door. Suppose paths are drawn on (or for clarity, above) this interval, which start and finish in subintervals (‘rooms’) with exactly one door (you should sketch some explicit examples). Relate the number of subintervals with a different labelling at each endpoint to the number of paths. Hence what can be said about the parity of the number of subintervals with a different labelling at each endpoint. (b) Explain how the result in the box can be deduced from this result by removing the rightmost string of zeros. Q2: The objective of this exercise is to show that it is not possible to tile an 8 × 8 square board with 2× 1 rectangular tiles, if the board has its top left and bottom right squares removed. (a) Think of the 8× 8 square board as being coloured with a chess board pattern. After removing the specified squares, how may squares of each colour remain? (b) How many squares of each colour must a 2× 1 rectangular tile cover? (c) Use your answers to (a) and (b) to deduce the result. Q3: Consider a black and white colouring of an 8× 8 square board which has an even number of black squares in total. (a) Show that reversing the colour of all the squares in any row or column again gives an even number of black squares in total. (b) Deduce from (a) that it is not possible to end up with exactly one black square by this procedure. Q4: In each square of a 5 × 5 square board coloured as for a chess board, suppose there is a spider. Each spider crawls simultaneously to a neighbouring square. Decide if this results in at least one square becoming empty. 20 Q5: A Delannoy path from (0, 0) to (m,n) in the lattice N20 is a lattice path using the step set S = {(1, 0), (0, 1), (1, 1)}. The number of such paths is the Delannoy number Dm,n. (a) Derive a recurrence relation for Dm,n (including boundary conditions). (b) Calculate the grid counts up to m,n ≤ 4. (c) Repeat the calculation from (b) for paths that never go below the line y = x. (d) By inspection express the counts from (c) in terms of Dm,n and one other Delannoy number. (e) Give a combinatorial proof that Dm,n = ∑ k≥0 ( m k )( n+ k m ) . [Hint: Partition the set of paths by the number of diagonal steps] Q6: Consider the subset of binomial paths which start at the origin and end at vertex (n, n+h) subject to the following two conditions (1) No vertices are allowed below the line y = x. (2) No vertices are allowed above the line y = x+ c, with c fixed and c ≥ 1. Denote this subset by Bhn(c) – these are “ballot paths in a strip”. (a) Draw the paths in B31(3), B 1 2(3) and B 2 2(3). (b) Generalise (or restrict) the ballot triangle to generate ballot paths in a strip i.e. place the counts |Bhn(3)| on the appropriate vertices in the domain {y ≥ x} ∩ {y ≤ x+ 3} ∩ {x ≥ 0} for at least n ≤ 3. Conjecture the value of |B0n(3)|. (c) Consider the ‘transfer’ matrix T and vector v0 T = ( 0 1 1 1 ) , v0 = ( 1 2 ) , Compute the vectors vm = T m v0 for several values of m and compare the results with the ballot strip numbers of (b). Based on your observations make a conjecture for how the value of |B0n(3)| is related to vm. (d) By finding the eigenvalues and vectors of T derive an expression for |B0n(3)|. 21 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 6: Difference Equations and Generating Functions • First order difference equations with coefficients independent of n are of the form xn+1 = g(xn). One initial value, say x0, must be specified for a unique solution. • Second order difference equations with coefficients independent of n are of the form xn+1 = f(xn, xn−1). Two consecutive initial values, say x0 and x1, must be specified for a unique solution. Q1: Let An denote the number of arrangements of {1, 2, . . . , n}. (a) Suppose all arrangements of {1, 2, . . . , n} have been listed. Explain how this list can be extended to a list of all arrangements of {1, 2, . . . , n+ 1}. Hence deduce that An+1 = (n+ 1)An. (b) What is the value of A1? Verify that the solution of the difference equation subject to this initial condition is An = n!. Q2: Let Bn,k denote the number of ordered k-tuples with distinct entires which can be formed from a set of n elements. (a) Suppose all k-tuples, k < n of {1, 2, . . . , n} have been listed. Explain how this list can be extended to a list of all (k + 1)-tuples, and hence deduce the recurrence Bn,k+1 = (n− k)Bn,k (k = 1, . . . , n− 1). (b) What is the value of Bn,1? Verify that the solution of the difference equation subject to this initial condition is Bn,k = n! (n− k)! . Q3: Consider the recurrence an = 5an−1 − 6an−2, n = 3, 4, . . . , with a1 = 1, a2 = 5. (a) Define the generating function A(x) = ∞∑ n=0 anx n. Explain why it is consistent to take a0 = 0. Use the recurrence to show A(x) = x 1− 5x+ 6x2 . (b) Using the method of partial fractions, and the geometric series, deduce from (a) that an = 3 n − 2n. 22 The generating function for the number of combinations of k numbers from {1, 2, . . . , n} is (1 + x)n = n∑ k=0 (n k ) xk. Here each factor of (1 + x) corresponds to a member of the set, where the x is the option of choosing that member, and the 1 is the option of not choosing that member. Q4: Let ar denote the number of combinations of r pieces of fruit from 2 apples, 1 pear, 2 oranges and a banana. (a) Explain why the generating function is (1 + x+ x2)(1 + x)(1 + x+ x2)(1 + x). (b) By expanding this out, compute {ar}r=0,1,...,6. Q5: Let ar be the number of ways of distributing r identical objects into n distinct boxes. (a) Explain why the generating function is (1 + x+ x2 + x3 + · · · )n. (b) Use the geometric series to rewrite this as( 1 1− x )n . (c) Use a Taylor series about the origin to show that for general real numbers α, (1 + x)α = ∞∑ p=0 α(α− 1) · · · (α− p+ 1) p! xp. (d) Use your answer to (c) to conclude that for n a positive integer ( 1 1− x )n = ∞∑ r=0 (n+ r − 1 r ) xr and relate this to your prior knowledge of ar. 23 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 7: Fibonacci The Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . satisfies the recurrence Fn = Fn−1 + Fn−2 subject to the initial condition F1 = F2 = 1. Associated with Fibonacci’s rabbit problem is a letter sequence of A’s and a’s. Starting with a single letter a, it can be generated recursively by the substitution A 7→ Aa, a 7→ A. Q1: Stairs consisting of n steps are to be climbed. Compute the number of ways, Sn, this can be done if the stairs can be climbed by taking either one step or two steps at a time. (a) Write down the values of S1 and S2. (b) By considering the reduction in the number of steps which remain to be climbed after an initial step of size 1 or of size 2, deduce that Sn = Sn−1 + Sn−2 and hence relate {Sn} to {Fn}. Q2: Consider a 2× n square grid. The problem is to calculate the number of tilings by 2× 1 rectangles (horizontal or vertical). Let this number be Un. (a) Write down the values of U1 and U2. (b) By considering the grid which remains after placing the 2 × 1 rectangle vertically, and then horizontally, in the left column of the 2×n grid, deduce Un = Un−1 +Un−2, and hence relate {Un} to {Fn}. Q3: Consider a sequence of n letters, each of which is either an A or B and suppose no two A’s are in succession. Find a recurrence for the number of such sequences, say, ln, and calculate ln in terms of a Fibonacci number. Q4: There are many combinatorial interpretations of the Fibonacci numbers Fn. From lectures we have that Fn+1 counts the number of tilings of an n-board with squares and dominoes. Give bijective proofs that the counting problems below are equivalent to this tiling problem (we just need the bijection itself and a brief argument why it works). (a) For n ≥ 0, Fn+2 counts the number of binary words with no consecutive 0s. (b) For n ≥ 1, Fn+1 counts the number of ways to arrange the numbers 1 through n so that for each 1 ≤ i ≤ n the number appearing in position i is either i− 1, i or i+ 1. (c) For n ≥ 1, Fn counts the number of tilings of an n-board with tiles of odd length. 24 Q5: The Fibonacci sequence {Fn} (we use that F0 = 0) has generating function F (x) = ∞∑ n=0 Fnx n = x 1− x− x2 . (a) Derive a simple, closed form expression for the function G(x) = ∞∑ n=0 gnx n, where gn = F0 + F1 + F2 + · · ·+ Fn, n ≥ 0 (b) Derive a simple, closed form expression for the function H(x) = ∞∑ n=0 hnx n, where hn = Fn+2 − 1, n ≥ 0 (c) Show that G(x) = H(x), and hence prove the identity F0 + F1 + F2 + · · ·+ Fn = Fn+2 − 1, n ≥ 0 Q6: Consider a positive integer p. Suppose we subtract from p the largest Fibonacci number Fn1 not exceeding p. (a) Show that 0 ≤ p− Fn1 ≤ Fn1−1 − 1. (b) Use (a) to conclude that by repeating this process, any positive integer p can be written in terms of the Fibonacci numbers F2, F3, F4, . . . , taking each one at most once and no two in succession. (c) Write out the explicit Fibonacci number decomposition according to this procedure for the integers 1 up to 12 inclusive. Let the smallest number in the decomposition be Fn∗ . If n ∗ is even associate with the integer p the symbol A, while if n∗ is odd, associate the symbol a. Form a letter sequence with 12 members from these symbols by writing them in succession. Demonstrate that after making the substitutions A 7→ Aa, a 7→ A, the first 12 members are unchanged. Comment then on the relation between this letter sequence and the letter sequence obtained from the Fibonacci rabbit problem. 25 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 8: Catalan and Functional Equations The nth Catalan number is 1 n + 1 ( 2n n ) . These numbers satisfy the recurrence an = a0an−1 + a1an−2 + · · ·+ an−1a0. The corresponding generating function C(x) = ∞∑ n=0 anx n satisfies the functional equation C(x) = 1 + x2C(x)2. Q1: Consider a sequence of n A’s and n B’s. Show that the number of arrangements of these symbols such that when we read left to right the number of A’s is always greater than or equal to the number of B’s is given by the nth Catalan number. Q2: The perimeter of a circle is divided into 2n intervals of equal length. A vertex is inserted at the end-points of the intervals. These vertices are then labelled from 1 to 2n counter- clockwise around the circle. Each vertex is connected by an edge or chord to exactly one other vertex such that the chords do not intersect. Let cn denote the number of such non-intersecting chord diagrams. (a) Draw all chord diagrams for n = 1, 2, 3. (b) Prove that any chord must connect points of different parity, i.e., any chord connects a point with an even label to a point with an odd label. (c) State a bijection between chord diagrams and balanced parenthesis. List the corresponding balanced parenthesis under the diagrams in (a). (d) Working solely with chord diagrams (but possibly guided by your knowledge of balanced parenthesis) prove that cn are Catalan numbers (you may show that cn satisfies the Catalan recurrence or that their generating function satisfies the Catalan functional equation). 26 Q3: Take a circle with n points on its the perimeter labelled from 1 to n in order. Draw lines between random points such that none of the lines intersect (not all points need be connected). Let cn denote the number of such non-intersecting chord diagrams on n points. (a) Draw all possible diagrams on n = 4 points. (b) Give a bijection between this problem and Motzkin paths (lattice paths on the square grid with step-set {(1, 1), (1,−1), (1, 0)}). (c) Show that the generating function C(x) = ∞∑ n=0 cnx n satisfies the functional equation C(x) = 1 + xC(x) + x2(C(x))2. Q4: Consider a lattice path of length n and let ln denote the number of paths. The associated generating function is L(x) = ∞∑ n=0 lnx n. From lectures we know that x d dx L(x) is the generating function of these lattice paths with one marked step. Give combinatorial interpretations of the formal power-series xk dk dxk L(x) and ( x d dx )k L(x). What is the interpretation if we also divide by k!? Q5: The generating function for binomial paths is B(x, y) = 1/(1 − x − y), where x and y ‘count’ East and North steps. Using the results from the previous question find the generating functions for binomial paths with (a) A single marked East step. (b) A marked East step and a marked North step. (c) Three marked East steps. Q6: The Catalan numbers Cn = 1 n+ 1 ( 2n n ) have generating function C(x) = ∞∑ n=0 1 n+ 1 ( 2n n ) xn = 1 2x ( 1− √ 1− 4x ) . (a) Use the above result and methods of formal power series to show that ∞∑ n=0 ( 2n n ) xn = 1 √ 1− 4x . (b) Let {an} be a sequence such that n∑ k=0 akan−k = 1. Calculate the generating function of the sequence and use the result from (a) to find an exact expression for an. 27 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 9: Permutations The two-line notation of a permutation tells us that integer j, j ∈ {1, 2, . . . n}, maps to integer P (j). The mapping can be displayed in two- line notation, and also as cycles. The standard correspondence between arrangements and permutations (as bijections) is a1a2 . . . an ←→ ( 1 2 · · · n a1 a2 · · · an ) A cycle of length 2 is called a transposition. In general (a1a2 · · · ar) = (a1ar)(a1ar−1) · · · (a1a2) The sign of a permutation σ, often denoted sgn(σ), is equal to +1 if σ consists of an even number of transpositions, and is equal to −1 if consists of an odd number of transpositions. It satisfies the factorization identity sgn(σρ) = sgn(σ)sgn(ρ). Q1: Write the following permutations in two-line notation, in terms of disjoint cycles, and also in terms of transpositions – note this form is not unique. (a) 264351 (b) 315642 Q2: (a) Use an appropriate formula from the above box to determine the sign of an r-cycle. Hence what is the corresponding parity? (b) Write in cycle notation the following permutations: 87654321 46213875. (c) Determine the parity of the permutations in (b). (d) Write the following cycles corresponding to permutations of {1, 2, . . . , 8} in two-line notation. (156)(247)(38) (1587)(23)(46). 28 The elementary transpositions are the 2-cycles interchanging i and i+ 1, si = (i i+ 1). All permutations can be written (non-uniquely) as a composition of elemen- tary transpositions. Q3: Calculate the two line notation of the permutations of {1, 2, . . . , 6} corresponding to the products (ie. composition) of elementary transpositions s5s4s3s1s2s1 s4s3s4s3s5s4s5. The set of all even permutations of {1, 2, . . . , n} forms a group referred to as the alternating group An. This group is generated by 3-cycles of the form (k k + 1 k + 2) for k = 1, . . . , n− 2. Q4: Calculate the two line notation of the permutations of {1, 2, 3, 4} corresponding to the products of 3-cycles (123)(234)(324) (213)(324)(324). The Stirling numbers of the first kind, S1(n, k), count the number of ways to seat n people at k identical tables. Equivalently, S1(n, k) is equal to the number of ways to write a permutation of {1, 2, . . . , n} as k disjoint cycles. They satisfy the recurrence S1(n, k) = S1(n− 1, k − 1) + (n− 1)S1(n− 1, k). Q5: Introduce the generating function An(x) = n∑ k=0 S1(n, k)x k. (a) By using the recurrence, and the facts that S1(n− 1, n) = S1(n− 1,−1) = 0, show An(x) = (x+ n− 1)An−1(x). (b) Note that A0(x) = 1, and use this to iterate the above first order difference equation and thus derive An(x) = x(x+ 1)(x+ 2) · · · (x+ n− 1). Q6: Using only combinatorial arguments find a formula for S1(n, n− 2) in terms of binomial coefficients. Explicitly check the formula for n ≤ 5. 29 The University of Melbourne — School of Mathematics and Statistics MAST30012 Discrete Mathematics — Semester 2, 2021 Practice Class 10: Symmetric Group and Applications The symmetric group Sn can be generated by the elementary transpositions {si}i=1,...,n−1 where si = (i i + 1), while the alternating group An can be generated by the 3-cycles {(k k + 1 k + 2)}k=1,...,n−2. Q1: (a) Suppose i < j. Then in general (i j) = sj−1sj−2 · · · si+1sisi+1 · · · sj−2sj−1. Check that the RHS has the same parity as the LHS. (b) Illustrate the formula of (a) in the cases (i j) = (25), (ij) = (16), by exhibiting their composition on the right and their composition on the left of the ordered pairs on the arrangement 213564. (c) Show that (k + 1 k k + 2) = (k k + 1 k + 2)−1 = (k k + 1 k + 2)2. (d) Write down the elements of A3 in terms of the 3-cycle (123). Q2: Calculate the two-line notation of the permutation of {1, 2, . . . , 7} corresponding to the elementary transpositions s5s1s2s1, s4s5s4s5s1s2s1s4 Use algebraic relations to show that the second permutation equals the first. An inversion of a permutation σ is a pair of integers (i, j) such that i < j and σi > σj.
Q3: Let σ = 42153 be a permutation of {1, 2, . . . , 5}.
(a) Draw the bipartite graph corresponding to σ.
(b) How many inversions does σ have?
(c) Write σ as a product of elementary transpositions and draw a picture of the corre-
sponding bipartite graph.
(d) Use (c) to find the set Iσ of inversions of σ.
30
The 15-puzzle, or any of its analogues for a m × n rectangle, can be rear-
ranged to all positions which require an even permutation, assuming the
blank returns to its initial position.
Q4: In the following 7-puzzles, can the numbers 1 to 4 in order be arranged along the top row,
and the numbers 5 to 7 in order be arranged along the bottom row?
(a)
6 5 1 2
4 7 3
(b)
4 1 7
6 3 2 5
(c)
7 6 5
4 3 2 1
Q5: In a 15-puzzle, are the following board positions related by sliding moves?
7 4 3 6
9 5 12 15
1 10 13
14 2 11 8
14 12 9 10
8 11 13 15
6 3 7 2
1 5 4
Q6: In the following letter version of the 15-puzzle, can an arrangement be found which has
the last line reading P L A �?
R A T E
Y O U R
M I N D
P A L
31
The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 11: Designs
A design consists of subsets of a set, with each subset containing the
same number (> 1) of elements. Also, it is required that each pair of
elements is in the same number of subsets.
Q1: Consider the design
{1, 2, 3} {4, 5, 6} {7, 8, 9} {1, 4, 7} {1, 5, 9} {2, 5, 8}
{3, 6, 9} {2, 6, 7} {3, 4, 8} {1, 6, 8} {2, 4, 9} {3, 5, 7}.
Explain how this could be used to rate the relative merits of 9 brands of detergents with
the help of 3 households on 4 consecutive days.
Associated with a design are the parameters (b, v, r, k, λ) where b = number
of subsets (blocks); v = number of elements (varieties); r = number of
subsets containing any one element; k = number of elements in each subset;
λ = number of subsets containing any given pair of elements.
Q2: From your notes write down two equations relating these parameters. Hence show that
there does not exist a (12, 8, 3, 2, 1) design.
Q3: Classify the design
{a, b, c}, {a, b, d}, {a, c, e}, {a, d, f}, {a, e, f}, {b, c, f},
{b, d, e}, {b, e, f}, {c, d, e}, {c, d, f},
according to the parameters (b, v, r, k, λ) and check the two equations noted in Q2.
Each subset can be encoded as a v-component array of 1’s or 0’s according
to it containing the elements {1, 2, . . . , v} in order, and from this a b × v
matrix formed. This matrix is called the incidence matrix of the design.
Q4: For the design in Q3 construct the incidence matrix. Now replace each 1 by 0, and each
0 by 1. Does this, referred to as the complement, represent a design? If so, what are its
parameters?
32
Let I denote the v × v identity matrix, and let J denote the v × v
matrix of all 1’s. For a square design, in which v = b (and thus k = r),
MTM = (k − λ)I + λJ.
Q5: The objective of this exercise is to show that for a square design
MTM = MMT .
(a) We know that det(MTM) > 0. Use this to conclude that M is invertible.
(b) Verify that MJ = kJ , JM = kJ , and thus MJ = JM .
(c) Starting with the equation
MMT = M(MTM)M−1,
substitute for MTM using the equation in the box, and use too the result of (b), to
obtain
MMT = (k − λ)I + λJ.
Thus deduce the sought result.
33