代写MAST30012、Java,c++程序代写

日期：2022-09-12 01:27

School of Mathematics and Statistics

MAST30012 Discrete Mathematics

Semester 2, 2022

Assignment 2

Due 5pm Friday September 23

Student Name Student Number

Tutor’s Name Practice Class Day/Time

Submit your assignment online in Gradescope.

Please attach this cover sheet to your assignment or use a blank sheet of paper as the

first page of your assignment with Student Name, Student Number, Tutor’s Name,

Practice Class Day/Time clearly stated.

Late submission will not be accepted unless accompanied by a medical certificate (or a similar

special consideration). If there are extenuating circumstances you need to contact your lecturer,

preferably prior to the submission deadline. Medical certificates are usually required.

You can handwrite or typeset your assignment. If handwriting, please make sure your pho-

tos/scan are clearly legible.

Full working must be shown in your solutions.

Marks will be deducted for incomplete working, insufficient justification or incorrect notation.

Unless otherwise stated, proofs of identities etc. must use combinatorial arguments.

There are 4 questions worth a total of 40 marks.

Q1: (10 marks)

(a) The game of Sim is played as follows. n dots are drawn on a piece of paper, and lines are drawn

joining each pair of dots. Two players take turns colouring an uncoloured line (one red, the

other blue). The first player to colour a triangle (the three lines joining three dots) in their own

colour is the loser. If all lines are coloured with no single-colour triangle, the game is a draw.

i. What is the largest number n for which Sim can end in a draw? (You may use results from

lectures, but you must still clearly explain your answer.)

ii. Three-player Sim works in the same way, but with three players (using colours red, blue

and green). What is the largest number n for which three-player Sim can end in a draw

(i.e. no one loses)?

(b) Prove that the Ramsey number R(3, 6) ≤ 19. You may use results from lectures, including the

other Ramsey numbers R(a, b) with a < 3 or b < 6. (Note that in fact R(3, 6) < 19 but do not

attempt to prove this.)

(c) Prove that the generalised Ramsey number R(2, a, b) = R(a, b).

Q2: (14 marks)

Recall that a binomial path is a lattice path which starts at the origin (0, 0) and takes steps from

S = {(1, 0), (0, 1)} = {E,N}. A 2-coloured binomial path is one for which there are two types of E

steps, red and blue, which we denote as Er and Eb (but still only one type of N step). For example,

there are two binomial paths which end at (1, 1), namely EN and NE, but there are four 2-coloured

paths, namely ErN, EbN, NEr and NEb. Let Ji,j be the number of 2-coloured binomial paths ending

at (i, j).

(a) Copy the following grid, where the bottom left corner represents the origin (0, 0). At each point

(i, j), write down the number Ji,j.

(b) Find a formula for the number Ji,j of 2-coloured binomial paths ending at (i, j).

(c) Repeat part (a) but now for 2-coloured ballot paths, where paths may not step below the main

diagonal.

(d) Let T hm be the set of 2-coloured ballot paths which end at (m,m+ h). Write down a recurrence

for |T hm|. Don’t forget to include initial / boundary conditions.

(e) The formula you found in (b) generalises to 2-coloured ballot paths, using the counts |Bhm| for

regular ballot paths, in an obvious way (if it is not obvious, check your answer to (b) again).

Nevertheless there is also a way to compute |T hm| using the same kind of reflection principle

that we used to count regular ballot paths. Explain this reflection principle, and use it to write

down an expression for |T hm| in terms of two different Ji,j.

Q3: (10 marks)

Consider the recurrence relation

an+3 = 3an+1 ? 2an

with a0 = 1, a1 = 1, a2 = 3.

(a) Calculate an for n ≤ 6.

(b) Prove that the generating function

A(x) =

∑

n≥0

anx

n =

1 + x

(1? x)2(1 + 2x) .

(c) Use a partial fraction expansion of A(x) to find an explicit expression for an.

Q4: (6 marks)

We have seen that the Fibonacci numbers Fn count many different combinatorial objects. For

example, Fn+1 is the number of ways to tile an n-board with monomers and dimers.

(a) Use a bijection with monomer-dimer tilings to show that the number of subsets of {1, 2, . . . , n}

with no consecutive numbers (including the empty set) is Fn+2.

(b) Use your answer to (a) to show that the number of subsets of {1, 2, . . . , n} with no consecutive

numbers (including the empty set), where we also regard n and 1 as consecutive, is Fn?1+Fn+1.