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

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.
• For the topic of generating functions I wrote a short book that includes videos that summarize the text.
An Introduction to Ordinary Generating Functions
• I have taught this course four times before (2003, 2012, 2014, 2017). The other times I taught the course I took detailed notes and updated them as I went along:
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.
• Homework assignments:

## 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:
• $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\cdot 3 + 2 \cdot 4 + 3 \cdot 5 + \cdots + n \cdot (n+2) =$
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.