Semester 2 Assessment, 2018
School of Mathematics and Statistics MAST30012 Discrete Mathematics Writing time: 3 hours
Reading time: 15 minutes
This is NOT an open book exam
Copyright By PowCoder代写 加微信 powcoder
This paper consists of 5 pages (including this page)
Authorised Materials
• Mobile phones, smart watches and internet or communication devices are forbidden. • No materials are authorised.
• No written or printed materials may be brought into the examination.
• No calculators of any kind may be brought into the examination.
Instructions to Students
• You must NOT remove this question paper at the conclusion of the examination.
• You should attempt all questions. Marks for individual questions are shown.
• Marks are allocated to working, mathematical accuracy and clarity of proofs.
• When appropriate answers may be given in terms of binomial or multinomial coe cients or other simple expressions.
• If you have any written or printed material related to the subject in your possession, you should immediately surrender it to an invigilator.
• The total number of marks available is 120.
Instructions to Invigilators
• Students must NOT remove this question paper at the conclusion of the examination. • Initially, students are to receive a 14 page script booklet.
• No special materials are to be supplied.
This paper may be held in the Baillieu Library
Student Number
Blank page (ignored in page numbering)
MAST30012 Semester 2, 2018
Question 1 (14 marks)
(a) Consider three pairs of shoes, the first pair are blue, the second pair red and the third pair green. How many ways can the shoes be arranged on a shoe rack (ie. in a line) such the blue pair are always next to each other? Left and right shoes are considered di↵erent.
(b) Consider a group of 23 people from which two equal sized teams and one referee are to be chosen. Give two clearly di↵erent methods to calculate how many possible ways this can be done.
(c) How many ways can the letters of the word “ADIABAT” be rearranged so that no two ‘A’s are adjacent.
(d) Let[6]={1,2,3,4,5,6}andD={(d1,d2)2[6]⇥[6] : d1 d2}betheoutcomesetwith all the events Ti,j = {(di,dj)} for all (di,dj) 2 D equally probable.
(i) What is the probability of the event {(1, 1)}?
(ii) What is the probability of getting a pair (d1, d2) such that d1 + d2 = 7 ( ie. the event
{(d1, d2) 2 D : d1 + d2 = 7})?
Question 2 (14 marks)
(a) Give a count-two-ways proof of the identity:
k✓n◆ = n✓n 1◆ .
(b) Give a bijective proof of the following identities:
Xn ✓ n ◆ n Xn ✓ n ◆ n 1 i) k=2 ii)kk=n2.
In your bijective proofs you need only define the two sets and the bijection between them – there is no need to prove your map is a bijection.
The two sets must be clearly di↵erent sets.
(c) Give a brief combinatorial (ie. not algebraic) argument that explains the identity
(2k + 1) = n2 ,
that is, that the sum of the first n positive odd integers is a square.
Page 2 of 5 pages
MAST30012 Semester 2, 2018
Question 3 (8 marks)
(a) A bag contains a certain number of multicoloured marbles. Each marble contains up to three of the colours: red, green and blue. It is known that 14 marbles contain red, 11 marbles contain blue, 11 marbles contain green, 6 marbles contain red and blue, 5 marbles contain red and green, 5 marbles contain blue and green, and 3 contain all three colours.
Using inclusion-exclusion determine how many marbles are in the bag.
(b) Using inclusion-exclusion and subtraction theorems, find how many ways three di↵erent coloured balls (one red, one green and one blue) can be placed into three coloured boxes (one red, one green and one blue) such that:
(i) each box contains exactly one ball, and
(ii) none of the boxes contain a ball of the same colour.
Verify your answer by listing all configurations.
Question 4 (10 marks)
(a) Define the Stirling number of the first kind, S1(n,k) and give a combinatorial interpreta- tion in terms of people seated at tables.
(b) Use the table seating interpretation to argue that S1(n,k) satisfies the partial di↵erence equation
S1(n, k) = (n 1) S1(n 1, k) + S1(n 1, k 1) , with S1(n,0) = 0, S1(n,n) = 1.
(c) Compute all the Stirling numbers S1(3,k), either by using the partial di↵erence equation or by finding all the corresponding permutations.
Question 5 (12 marks)
(a) Define the Ramsey number R(a, b) using the coloured complete graph interpretation.
(b) State and prove the theorem for R(n, 2).
(c) Consider a regular hexagon (6 sided polygon) with all sides having length two. If seven points are placed at random inside the polygon prove (or disprove) that at least two points must be a distance no more than two apart.
(d) Consider an interval with the two endpoints labelled 0 and 1 respectively. Suppose that the interval is broken up into subintervals , with each endpoint labelled by 0 or 1 at random. Show that the number of subintervals labelled (0,1) minus the number of subintervals labelled (1, 0) is equal to 1.
Page 3 of 5 pages
MAST30012 Semester 2, 2018
Question 6 (12 marks)
(a) Let the sequence (an)n 0 satisfy the recurrence relation 12an+2=7an+1 an, Pa0=a1=2.
(i) Show that the generating function G(x) = 1n=0 anxn is a rational function (ie. a ratio of polynomials).
(ii) Using a partial fraction expansion find an exact expression for an.
(b) Assuming the sequence (bn)n 0 has generating function
H(x) = 1 + x
find the recurrence relation satisfied by bn.
Question 7 (12 marks)
(a) Draw all the monomer-dimer pavings of a 4-board.
(b) Prove that the number of monomer-dimer pavings of an n-board, Pn satisfies the recur- rence relation
Pn+2 = Pn+1 + Pn
with P1 = 1, P2 = 2. If you use a bijective map you only need show it is well defined.
(c) Find the generating function, P(x) = P1n=1 Pnxn, where Pn is the number of monomer- dimer pavings of an n-board.
(d) Using the generating function obtained in part (c) express Pn as a sum of binomial coef- ficients. Hint: it is simpler to start with 1 + P (x).
Question 8 (16 marks)
(a) Consider the two permutations = 23145 and ⌧ = 24531.
(i) Write as a two-line array and in standard cycle form. (ii) Write 1 in standard cycle form.
(iii) Write ⌧ as a two-line array. (iv) Find the set of inversions of ⌧.
(v) Calculate sgn(⌧).
(vi) Write as a composition of simple transpositions
(b) Let ↵ and be permutations of {1,2,…,n}. Prove that sgn(↵ ) = sgn(↵) sgn( ) .
You may use any theorems from lectures.
Page 4 of 5 pages
MAST30012 Semester 2, 2018
Question 9 (12 marks)
(a) Using the snake-pattern labelling of the squares of the 7-puzzle (the blank cell is grey), compute the permutation, in cycle notation, corresponding to the move μ2 given by
What is the parity of μ2?
(b) Consider the product of simple transpositions s5s4s3s5s2. Determine where each of the
numbers 1, 2, 3, 4, 5, 6 are mapped to and write the permutation as a two-line array.
(c) Write down the three algebraic relations that simple transpositions satisfy and use these
to find the set of reduced word decompositions of
= s4s2s3s2s1.
Question 10 (10 marks)
(a) Draw the five Dyck paths with six steps. For each path find the complete binary tree the path bijects to. Draw at least one intermediate diagram showing how you found each tree.
The bijection must depend on the path structure alone and not arise simply by listing the complete binary trees.
(b) Take 2n nodes in a line and join them above the line by ‘arches’. An arch connects exactly two distinct nodes and no two arches intersect. There are five arch diagrams on six nodes:
Find a bijection from the five arches on six nodes to the set of six step Dyck paths. Give a brief explanation of your map (it is not necessary to prove it is a bijection).
End of Exam—Total Available Marks = 120
Page 5 of 5 pages
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com