Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 2

MATH1064: Discrete Mathematics for Computation

Semester 2, 2022

(b)  Does the statement “p | (k(p))” remain true for arbitrary positive integers p? Justify

your answer.

(c)  Let p be a prime number and let k be an integer satisfying 1 ≤ k ≤ p − 1. Use the statement “p | (k(p))” from the first part to deduce that

(x + y)p  ≡ xp + yp      mod p                                       (1)

for all x,y ∈ Z. Show all your working.

(d)  Find the last digit of 72022 . Show all your working.

2.  Diagrams are constructed using the following procedure.   First, a rectangle is drawn. Then exactly n points are marked along the top edge of the rectangle, and exactly n points are marked along the bottom edge of the rectangle. These points are then joined by curves such that

1.  no curve can leave the rectangle;

2.  no curve intersects any other curve; and

3.  each of the 2n points is joined by a curve to exactly one other of the 2n points.

A diagram following these rules is called a valid diagram with 2n marked points.  Two valid diagrams are called equivalent if the n pairs of marked points connected by a curve are equal in both diagrams. Examples of valid diagrams for n = 1, 2, 3 are shown below.

Prove that the number of valid diagrams with 2n marked points is equal to the n-th Catalan number by

(a)  recovering the recurrence relation of the Catalan numbers from constructing valid

diagrams with 2n marked points from diagrams with fewer marked points.

(b)  constructing an explicit bijection between the set of valid diagrams with 2n marked

points (up to equivalence) and another collection of objects you have studied in lectures that is known to be enumerated by the n-th Catalan number.

Show all your working.

3.  Suppose a die has probability 0 ≤ p ≤ 1 of rolling a 1.

(a)  What is the probability of rolling a 1 exactly k times if the die is rolled exactly n

times? You may assume each roll is independent. Show all your working.

(b)  Determine the expected value for the number of times a 1 is rolled after exactly n

rolls. Show all your working.