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.






Grade:

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:







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: 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.