Math 4160: Combinatorial Mathematics - Fall 2019




Contact information:

Mike Zabrocki
Course will take place WC 118 - TR 2:30-3:45pm
Office: TEL/DB 2026
email: zabrocki@mathstat.yorku.ca
office hours: Monday 12-2pm and Thursday 1-2pm and by appointment
For the week of Dec 9-13 I will hold office hours Dec 11, from 10-noon. Additional office hours 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, Pólya'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:







Schedule:

Date
Topic
Remarks
Sept 5
Compute $1^k + 2^k + \cdots + n^k$
telescoping sums, notes
Sept 10
finish using Stirling numbers to compute $\sum_{i=1}^n i^k$

Sept 12
sets and multisets
Watch video: addition/multiplication principle
Sept 17
Set partitions, permutations
First assignment - due Oct 3
Sept 19
counting poker hands

Sept 24
combinatorial identities, beginning of g.f.s

Sept 26
generating functions for well known sequences

Oct 1
operations on g.f.s $\leftrightarrow$ operations on sequences

Oct 3
addition and multiplication princple of g.f.s

Oct 8
combinatorics and generating functions
Second assignment - due Oct 23
Oct 10
Partitions and generating functions
problems 1, problems 2
Oct 15 & 17
Reading Week

Oct 22
Discussion on hw2, partitions

Oct 24
Euler's pentagonal number theorem, exponential g.f.s

Oct 29
exponential generating functions
Third assignment - due Nov 13 (latex)
Oct 31
e.g.f.s and start of Polya counting
Midterm - due Nov 4 (latex)
Nov 5
Polya counting

Nov 7
Polya counting, orbit-stabilzer theorem

Nov 12
Burnsides Lemma and Polya counting

Nov 14
Example exponential generating function

Nov 19
Counting permutations with cycle structure

Nov 21
Euler phi function, beginning of Mobius inversion
Fourth assignment - due Dec 5 (latex)
Nov 26
Mobius inversion for integers and posets

Nov 28
proof of Mobius inversion on posets, Inclusion-Exclusion

Dec 3
Inclusion-Exclusion, final exam




Announcements:

(Sept. 2, 2019) The first day 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 in the second class.
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 17, 2019) I've posted the first assignment that will be due October 3, 2019.

(September 19, 2019) I've poseted a copy of this website as the syllabus for this course (pdf).

(Sept 24, 2019) I have office hours scheduled on Mondays, but I won't be available on Monday, October 21, 2019.

(October 5, 2019) I posted a new homework assignment today. I'll make it due after reading week (Oct 23), but get started early. The midterm will probably also be that week (take home) and so you don't want to double up on due dates. I also updated the first 4 chapters of notes by correcting typos and adding examples and exercises.

(October 18, 2019) Someone asked for the latex homework file and so I am making it available tex. Also...thread:

nobody told me about subitem!!! i've been nesting enumerates!! i just was like ooh it would be awesome if this worked, and then it did??

— 🔺ʻAʻOLE TMT🔺NO KIDSnCAGES (Dr Piper) (@pwr2dppl) October 15, 2019


(December 4, 2019) Details that we discussed about the final on the last day:
(1) It is take home and, like the midterm, you are not to discuss it with anyone else.
(2) The exam is 5 questions long and I believe it could be completed in roughly 3 hours (the questions are similar to those sorts of things that we have done in class, although it is heavy on the Polya counting). However, as a take home exam I want to give you the time to reflect on the problems and consult online resources if you want that.
(3) Because of the flexibility that we have, I will allow you to start the exam when you would like between the dates of December 6-December 13 (finishing 3 days later). Please email me and I will put your name on my calendar and I will send you the exam on that date in the morning. Again, I repeat that you should not exchange information with anyone else in the class even after you finish the exam.