CO 330, Fall 2017

Information

We will explore combinatorial classes by

• Meeting classical discrete objects
• Counting them
• Finding bijections between classes
• Generating random elements

Instructor: Karen Yeats
Office:MC 5126
Email: kayeats at uwaterloo.ca
Office Hours: Mondays 2:30-3:30 and Tuesdays 1:30-2:30.
Lectures: MWF 10:30-11:20 in MC 4041
Course Notes: Combinatorial Enumeration by David Wagner available from wherever course notes usually come from.

Announcements

• Syllabus.
• Instructor office hours decided: Mondays 2:30-3:30 and Tuesdays 1:30-2:30. Syllabus has been updated to reflect this.
• One of our TAs, Nick Olson-Harris (MC 5133) will have office hours on Wednesdays 1-2.
• Sifat Rahman, our other TA (MC 5023B) will have office hours on Fridays 1-2.
• The midterm (which is Friday October 20 in class) will be in room MC 2034.
• There was a typo in a3 which is now corrected.
• Over the reading days please read this. We will discuss it in class.
• The mistakes you found for assignment 4 question A1 are corrected. You might need to convince your browser to reload cached files to actually get them.
• No office hours Tuesday Oct 24 or Tuesday Oct 31 for admin duties and travelling respectively.
• Midterm solutions.
• There was a typo in one of the course notes questions for a6, please see the revised assignment for details.
• The text of assignment 7 has been modified to make it clear you can use either the maple or the python sample code.
• No office hours Monday Dec 4. I will have extra office hours December 13, 14, and 15 from 11 to noon. Email for other times.

Assignments

Assignments will be roughly weekly and typically due at 4pm on Wednesdays using Crowdmark.

1. Assignment 1, due Wednesday September 20 at 4pm on Crowdmark. Solutions.
2. Assignment 2, due Wednesday September 27 at 4pm on Crowdmark. Solutions.
3. Assignment 3, due Wednesday October 4 at 4pm on Crowdmark. Solutions.
4. Over the reading days please read this. We will discuss it in class.
5. Assignment 4, due FRIDAY October 13 at 4pm on Crowdmark. Friday October 13 is following a Wednesday schedule. Solutions.
6. Assignment 5, due Wednesday November 1 at 4pm on Crowdmark. Solutions.
7. Assignment 6, due Wednesday November 15 at 4pm on Crowdmark. Solutions.
8. Assignment 7, due Wednesday November 22 at 4pm on Crowdmark. Solutions.
9. Assignment 8, due Wednesday November 29 at 4pm on Crowdmark. Solutions.

Class Summaries

These summaries are not meant to replace either the printed course notes or your own class notes but give an overview and can help emphasize what the point was supposed to be and what was most important.

Part 1: combinatorial specifications, recursively defined classes and the Lagrange implicit function theorem. Key reference: course notes chapters 4, 6,7 and 8.

1. Lecture 1 summary.
2. Lecture 2 summary.
3. Lecture 3 summary.
4. Lecture 4 summary.
5. Lecture 5 summary.
6. Lecture 6 summary.
7. Lecture 7 summary and some maple examples.
8. Lecture 8 summary.
9. Lecture 9 summary.

Part 2: q-binomial coefficients and other q-analoques. Key reference: course notes chapters 2, 3 and 5.

1. Lecture 10 summary.
2. Lecture 11 summary.
3. Lecture 12 summary.
4. Lecture 13 summary.

Part 3: integer partitions. Key reference: course notes chapters 9 and 10.

1. Lecture 14 summary.
2. Lecture 15 summary.
3. Lecture 16 summary. This one isn't actually part of this topic because it was midterm review.
4. Friday October 20 was the midterm.
5. Lecture 17 summary.
6. Lecture 18 summary.
7. Lecture 19 summary.
8. Lecture 20 summary.
9. Lecture 21 summary.
10. Lecture 22 summary.

Part 4: Labelled objects and exponential generating functions. Key reference: notes from another course and our course notes chapter 11.

1. Lecture 23 summary.
2. Lecture 24 summary.
3. Lecture 25 summary.
4. Lecture 26 summary.
5. Lecture 27 summary.

Part 5: Random generation. No key reference, but see lectures 8 to 13 of another course.

1. Lecture 28 summary and the maple example and the same example in python.
2. Lecture 29 summary.
3. Lecture 30 summary, the maple and python without pointing and maple and python pointed for better performance.
4. Lecture 31 summary.
5. Lecture 32 summary.
6. Lecture 33 summary.
7. Lecture 34 summary.
8. Lecture 35 summary.