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