UNIVERSITY OF TORONTO

Faculty of Arts and Science

MAT344H1S Introduction to Combinatorics

Final Assignment

Due Tuesday April 14 at 10:00 pm

(to be submitted on Crowdmark)

Rules:

This assessment is subject to the University of Toronto Code of Behaviour on Academic

Matters, available at: https://governingcouncil.utoronto.ca/secretariat/

policies/code-behaviour-academic-matters-july-1-2019

It is your responsibility to be familiar and follow this code (in particular, see Section

B1). In addition, this assessment is subject to the following rules:

• You may use all official course material, i.e. your lecture and tutorial notes, the

videos, slides and other notes posted on our Quercus page, the textbook, the pre-

vious assignments in our course and their posted solutions. You may also use

your own term work.

• Any aid or resource (online or offline) other than those authorized above are not

permitted.

• During the assessment period do not communicate about the questions or mate-

rial on the assessment with any person other than a MAT344 course instructor.

• Do not post the questions or answers to them anywhere online or otherwise.

Every single paper will be investigated, and cases of academic misconduct will be

reported. Every year a handful of students are reported to OSAI (Office of Student Aca-

demic Integrity) and receive various penalties, which may range from an F in the course

to expulsion from the University.

Instructions:

• You must complete and sign the Honour Pledge on the next page before you start

working on the assessment. After you finish working on the assessment, you

must complete and sign the Declaration Form provided on the last page of the as-

sessment. The Honour Pledge and Declaration Form must be submitted (together

with the rest of the assessment) before the deadline. The assessment will be con-

sidered as not submitted if the Honour Pledge or Declaration Form is missing (or

is not completed and signed).

• The Honour Pledge, Declaration Form, and your answer to each question are to

be uploaded separately on Crowdmark before the deadline. In case of technical

issues, you must submit these by email to one of the course instructors before the

deadline. If you are sending your solutions to a course instructor, please only

attach one file per question (JPEG or PDF).

1

2Honour Pledge

I pledge to honour myself and my community by assuring that the work I do on this

assessment fully represents my own knowledge and ideas. I pledge to fully adhere to the

University of Toronto Code of Behaviour on Academic Matters and the rules listed on the

cover page of this assessment.

Full Name Student Number

Signature Date

3Problems

Note: All claims (including answers to questions starting with “determine” or “find”)

must be justified . Answers without or with wrong justification will not be given any

credit.

1. (6 points) A graph G is defined as follows: the set of vertices of G is the set of all

sequences of length 4 in {1, 2, 3} (thus G has 34 = 81 vertices). Two vertices of G

are adjacent if and only if the two sequences differ in exactly one position. So for

instance, 1123 and 1323 are adjacent, whereas 1123 and 2223 are not.

(a) Determine if G is Eulerian.

(b) Find the chromatic number of G.

2. (5 points) Let G be the same graph as in the previous question.

(a) Find the number of edges of G.

(b) Determine if G is planar.

3. (4 points) For any positive x, let f(x) be the number of elements of the set

{n ∈ Z : 0 < n ≤ x, n is not divisible by any of 2,3, and 7}.

Find lim

x→∞

f(x)

x

.

4. (5 points) Let n be a positive integer. Find the number of solutions to the equation

x1 + x2 + x3 = n

in Z subject to x1, x2, x3 ≥ 0, x1 even, and x2 odd.

5. (5 points) For n ≥ 1, let an =

n∏

r=1

(3r− 2). Set a0 = 1. Show that for every n ≥ 0,∑

k,`,m≥0

k+`+m=n

aka`am

k! `!m!

= 3n.

6. (5 points) Find a closed form formula for the sequence an defined by a0 = −9/4,

a1 = −23/4, and

an = an−1 + 2an−2 + 2n+ 3

n (n ≥ 2).

Inductive arguments will not be accepted.

7. (5 points) The sequence an is defined by a0 = 0 and

an = 1+

n∑

k=0

akan−k (n ≥ 1).

Find a non-recursive formula for an. (Your formula may involve a sum of terms

the number of which depends on n.)

4Declaration Form

Congratulations - you have made it to the end of your assessment for this course! We

hope that you feel proud of the work that you did here because you know that it was your

own and no one else’s. Please know that all suspected cases of academic dishonesty will

be investigated following the procedures outlined in the Code of Behaviour on Academic

Matters. If you have violated that Code or other rules of this assessment mentioned on the

cover page, admitting it now will significantly reduce any penalty you incur. Admitting

your mistakes is as much a matter of pride as never making them from the beginning.

Thus, please check the appropriate statement below and complete the rest of the form.

I confirm that the work I have done here is my own and no one else’s, and is in line

with the principles of scholarship and the University of Toronto Code of Behaviour on

Academic Matters, and with the rules given on the cover page of this assessment.

I regret that I violated the Code of Behaviour on Academic Matters or other rules of

this assessment and would like to admit that now so that I can take responsibility for my

mistake.

I confirm that my response here is an accurate and true representation of my behaviour,

knowing that by signing this declaration untruthfully I will incur an even greater penalty

if it is later discovered that I have cheated or behaved dishonestly on this assessment.

Full Name Student Number

Signature Date