WARNING THIS IS AN OLDER WEB PAGE FROM A COURSE GIVEN IN 2017 AND REMAINS POSTED HERE FOR REFERENCE ONLY The course webpage for the 2019 version of the course.Math 4160: Combinatorial Mathematics - Fall 2017

Contact information:

Mike Zabrocki
Course will take place CLH 110 - TR 2:30-3:45pm
Office: TEL 2026
email: zabrocki@mathstat.yorku.ca
office hours: Monday 12-1pm, Thursday 10-11am or by appointment

Course description:

Topics from algebra of sets, permutations, combinations, occupancy problems, partitions of integers, generating functions, combinatorial identities, recurrence relations, inclusion-exclusion principle, Polya's theory of counting, permanents, systems of distinct representatives, Latin rectangles, block designs, finite projective planes, Steiner triple systems. Prerequisites: SC/MATH 2022 3.00 or SC/MATH 2222 3.00; six credits from 3000-level mathematics courses without second digit 5; or permission of the course coordinator.

The main goal of this course will be to develop four common tools of combinatorics that are used to enumerate finite sets: basic counting principles, bijective arguments, Pólya Theory and generating functions. We will apply these tools to examine specific examples of combinatorial objects. The emphasis of assignments will be on problem solving and development of combinatorial techniques.

The grade for this course will mostly be based on homework assignments (55%). You may work together on these assignments, but I want you to hand in your own work (YOU must work on these problems and they will be compositions so I expect your answers to be original even if you worked with someone). There will be a midterm (20%) and a final (25%) and, although these assignments are take home, you will be expected to work on those problems on your own. You will be able to consult with me on the midterm and final. On the take home assignments I expect original work.

Course references:

• There is no required textbook for this course, but the material that we will cover can be found in many references. If you feel that you want a textbook, a good one that covers this is How to Count: An Introduction to Combinatorics.
• I have taught this course three times before (2003, 2012 and 2014). The last two times I taught the course I took detailed notes: from 2012 and there were some updates from 2014. I will probably not have the time to write detailed notes this year, but I might try to improve what I have into a better form if we cover similar topics.
• Most assignments in this course are more about writing than being able to calculate. You will need to LaTeX your assignments.
• When I do examples in class or in the notes I will sometimes augment a calculation with a calculation in the computer algebra system Sage (e.g. to take a coefficient in a series). Sage is free to download or you can access Sage online through the sage cell server or by opening a Cocalc account. You are welcome to use programs you are more familiar with (e.g. Maple, Matlab or Mathematica) to do the same calculations or there are specific online tools that can do these calculations.
• Other material for this course, announcements and grades will be on the course moodle.
• I will add notes here and will continue to update them. They are based on what I talk about in class and previous versions (2012 and 2014).
• Homework assignments:

WARNING THIS IS AN OLDER WEB PAGE FROM A COURSE GIVEN IN 2017 AND IS HERE FOR REFERENCE ONLY

Announcements:

(Sept. 7, 2017) (I'm writing this at 10am for a 2:30pm class) So today we are going to look at how combinatorics can be used to compute sums of the form $1^r+2^r+...+n^r$. We will just do a bit of experimenting and conjecturing today, but then I want you to go home, watch some videos and do some homework and we will get to the punchline next time.
Please watch the following videos: Then I would like you to to prove the following results using telescoping sums:
• $1^3+2^3+...+n^3 = \frac{n^2(n+1)^2}{4}$
• $1^4+2^4+...+n^4 = \frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$
• $(1)_k + (2)_k + ... + (n)_k = \frac{(n+1)_{k+1}}{k+1}$
Start typing up those in LaTeX. You don't have to hand it in next time, but you will hand it in when I give you your first homework assignment.

(Sept 7, 2017) In case you are interested in the sage commands that I used to compute $1^6+2^6+...+n^6$, I typed
[sum(i**6 for i in range(1,n+1)) for n in range(1, 11)]
and this gave me the first 10 terms of that sequence.

(Sept 21, 2017) I meant to post the homework yesterday, but there were (and still are) edits to do. The problems won't change, but I will add a few details so please check back. It will be due October 5, 2017. Homework #1. You will turn it in on the moodle in LaTeX/pdf format.

(Oct 5, 2017) I just posted the next homework assignment. It will be due in two weeks (Oct 25 ...corrected from Oct 19 and 23).

(Oct 6, 2017) Please copy the question that you are answering in your assignments. It is always so unclear when reading your assignments what an answer is referring to unless the complete question is there.

(Oct 12, 2017) Please figure out the answers to the matching worksheet for class today.

(Oct 12, 2017) The correct due date is October 25...corrected from Oct 23 and Oct 19 for the homework.

(Oct 12, 2017) I have a cleaner version of the proof of Euler's pentagonal number theorem that I presented roughly last time. A proof of this this result also appears in the recommended book "How to Count".

(Oct 19, 2017) I wrote up a full solution to the problem that we discussed in class today.

(Oct 20, 2017) I haven't had any time this week to finish the homework assignments. I'll start sending back your assignments. I pulled together some examples of what I was seeing to show that there was a range of "just great" (clear, complete, correct) to "really difficult to read." Here is a pdf where I pulled a few of these together.

(Oct 23, 2017) I uploaded feedback on your assignments. I won't be able to give quite so detailed remarks on future assignments, instead I will just give you a grade based on the types of remarks that I gave you here. I will give you until next Monday (Oct 30) to update your homework 1 (if you want). If you want to leave it as is, I will just grade the one that I have. Just as a reminder, I've extended the due date for the second assignment until Oct 25.

(Oct 31, 2017) I just posted the 3rd hw assignment (mostly on) exponential generating functions. It is due Nov 13 (but FYI, we also have the midterm this Thursday, Nov 2 - Monday, Nov 6)

(Nov 2, 2017) The midterm is available starting from 3pm today. It only has 3 problems. As you do this exam, I would like you to keep track of what references you consult (web pages, books, etc.). Please hand in the list with your midterm. Besides consultations with me, would like you to work alone on this assignment. I will have extra office hours for this class 11am-12pm on Friday November 3.

(Nov 17, 2017) Its late, but I want to post a version of the homework tonight, but it could potentially have some corrections.

(Nov 30, 2017) The final is posted. You have until December 8 to finish. If you have an early final schedule, I can extend the deadline, but I need to know in advance.

(Dec 2, 2017) I will hold office hours at the regularly scheduled times on Monday 12pm and Thursday 10am the week of December 4-8.

(Dec 4, 2017) Someone pointed out to me that question 3 did not mention that the expression we were looking was for colorings of the graph with k colors. I have corrected this.