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:

• 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:
  
  • Chapter 1: Finite Sums (10 pages)
  • Chapter 2: Counting using Recursion (8 pages)
  • Chapter 3: Counting using Bijections (10 pages)
  • Chapter 4: Generating Functions (41 pages)
  • Chapter 5: Exponential Generating Functions (13 pages)
  • Chapter 6: Pólya Enumeration (43 pages)
  • Chapter 7: Mobius Inversion and Inclusion-Exclusion (19 pages)
  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:
  • homework 1 - due Oct 3
  • homework 2 - due Oct 23
  • homework 3 - due Nov 13
  • homework 4 - due Dec 5

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:

• The addition and multiplication principles
• Telescoping sums
and make sure you read the page about writing your homework in LaTeX

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.