Official description:
Covers basic methods and results in combinatorial theory. Includes numeration methods, elementary properties of functions and relations, and graph theory. Emphasizes applications. Prerequisites: Requires prerequisite course of MATH 2001 (minimum grade C-).
My unofficial description:
Combinatorics is the study of enumeration, or counting. We will count all manner of mathematical objects, and study related ideas such as generating functions and graph theory. Along the way, we will focus on the skills of mathematical thinking and communication, and the art of proof writing.
Try a couple of the first exercises from Section 1. These have solutions, so you can check yourself.
Do Page 1 of the Pigeonhole worksheet from Wednesday at home, and bring it back to class on Friday. We may spend a bit more time with it in class Friday, so refrain from doing the rest at home (there are plenty of fun exercises in the text).
Tasks due Monday, August 31st (INCLUDING HAND-IN):
In class on Friday we discussed the worksheet problem about consecutive numbers, but I didn't write up a proof on the board, we just discussed. Write up a carefully written, nice proof of the following theorem, to hand in:
Theorem: If n+1 numbers are chosen (without repeats) from the list 1, 2, 3, ..., 2n, then at least two consecutive numbers have been chosen.
Also give an example of choosing n numbers such that none are consecutive.
You will be graded on writing as well as mathematical correctness.
Do some more problems from Chapter 1 on pigeonhole principle, as needed so that you feel confident.
Read Bóna, Section 2.1
Tasks due Wednesday, September 2nd:
Read Section 2.2 of Bóna. Make sure as you read example proofs, you are challenging yourself. Try to prove it before you read it, ask yourself key questions (where is this hypothesis being used? could we prove this by non-strong induction? why not? etc.), and so on.
Try a few of the Chapter 2 problems to begin writing your own induction proofs.
Tasks due Friday, September 4th:
Make sure to work on the 2-5-cent coin question from today's worksheet. It's not to hand in, just so we can talk about it at the beginning of next class.
Do some more induction problems from Bóna for practice.
Tasks due Monday, September 7th:
None, it's labour day.
Tasks due Wednesday, September 9th (INCLUDING QUIZ):
There will be an in-class quiz this day on pigeonhole/induction (Chapters 1 and 2 of Bóna). Review these topics and be prepared to do these two types of proof on the quiz.
Attempt the first 8 problems on this enumeration worksheet which I will take up at the beginning of class.
Start reading Chapter 3 of Bóna (this will also help with the above).
Tasks due Monday, September 14th (INCLUDING WORK TO HAND IN):
Finish reading Chapter 3 of Bóna and practice on the exercises as needed.
Assume that a convex n-gon is such that no three diagonals meet at a point. How many intersection points between diagonals are there? Note:
Please write up a neat solution to hand in. Writing will be graded along with math.
If the problem is unclear, email me to ask. If you're stuck, you can email for a hint.
On all written homework cite ALL sources of help you used. If none, say "Citations: none". Cite any website you looked at (by exact URL), name any people you discussed the problem with, and name any books that helped you (incl. page number), etc. For each source, indicate how it helped (e.g. "got the main idea from reading this site", "got the following hint from this person: ..." etc.) If you do not do this you will lose a point and I'll make you do it anyway. If you can't solve the problem by a good faith effort, you are allowed to consult resources but you must be explicit about their use, and you may not copy from them.
If you have a religious observance that interferes with this deadline, or any other important deadline, please let me know so we can make alternate arrangements.
Tasks due Wednesday, September 16th:
Start reading Chapter 4 of Bóna.
Tasks due Friday, September 18th:
Finish reading Chapter 4 of Bóna, and do some of the exercises. I recommend Exercise 3 -- which of our three proofs of Theorem 4.6 generalize? I also recommend 4 and 5 (combinatorial proofs; what are we counting?), . Try 26 just for facility with computations. Remember, the more exercises you do, the better you get at them!
Tasks due Monday, September 21st:
Friday in class I got the sense that the class needed to prepare more for the quiz. We had a worksheet, here; please try these problems before Monday and I will take them up in class. DO THEM. You will receive only 10% of the learning benefit if you show up not having struggled with them. This WILL reflect on your quiz. Note: the sheet references Stirling and Bell numbers, which are introduced in Def 5.5, and 5.11 in your book (my intention was to illustrate them at the board when people got there). Those problems on the sheet are actually taken from that chapter; you will benefit a lot less if you read the proofs there instead of struggling to create one yourself.
Tasks due Wednesday, September 23rd:
There will be a Wednesday quiz on Chapters 3 and 4.
It will consist of one combinatorial proof (similar to Theorems 4.3, 4.5, 4.7), and a few counting problems similar to those on the worksheets we've done. In particular, you may be asked to do counting problems like the six types in Table 3.1, but you will also be asked to JUSTIFY the formulas instead of calling on them as memorized formulas. Therefore study these examples carefully to understand their justification.
Tasks due Friday, September 25th:
Read Chapter 5 of Bóna, up to the end of 5.2.
Tasks due Monday, September 28th (HAND IN):
Homework problem due. The problem is as follows: Suppose g(n) counts the number of set partitions of [n] which involve no single-element blocks (i.e. all blocks have at least two elements). Show that g(n+1) = B(n) - g(n) (here, B(n) is the Bell number). Note: I'm looking for a bijective or combinatorial proof. That is, interpret each side of the equation as counting something, and then show that there's a bijection between the things they count. Another hint: do examples. You can email me for more hints.
Tasks due Wednesday, September 30th:
Please use some time for review on whatever topics you need. We are interweaving some generating functions into the enumeration; you could opt to read ahead about this in Bóna.
Tasks due Friday, October 2nd:
I never got around to giving homework because of my trip. Sorry! :)
Tasks due Monday, October 5th:
Finish to the end of Section 3 on the worksheet (available here) in preparation for class.
Read Bóna, Sections 5.3, 6.1 and 8.1.1.
In class today we'll review some of the stuff we've done so far, including solutions to the worksheet.
Tasks due Wednesday, October 7th:
Some suggested review problems: Exercises 1 and 2 of Chapter 8, Exercise 5, 6, 7 of Chapter 5, and Exercises 1, 2, 14 of Chapter 6. As well as reviewing your notes and worksheets.
In class we'll do example problems.
Tasks due Friday, October 9th:
Quiz! It will cover Chapter 5, 6.1 and the generating function topics we've done, 8.1.1. Please know how to find a generating function if I give you a recurrence relation.
Tasks due Monday, October 12th:
Work on the homework due Wednesday.
Tasks due Wednesday, October 14th:
Write the quiz (available here) that you wish you had handed in, i.e. complete a good copy of it as homework. Note: Many of you really didn't see what I was after with Problem 1. I was hoping you would plug in x=0 and obtain some information, then plug in x=1 and obtain some information, etc. You can ask for hints by email now. Remember to cite resources, as always.
Tasks due Friday, October 16th:
Read Chapter 7 of Bóna.
You may want to try Exercises, but be warned that there are not a lot of really great exercises, so you may be better off studying the chapter examples in detail and re-creating them. Still, the concrete ones (early supplementary exercises) are useful, as is the homework problem for Monday.
Puzzle: How can you recover Theorem 7.3 by choosing appropriate functions f and g in Theorem 7.6? This is a little tricky: the sets in one aren't the exactly the sets in the other. I'll give the answer at the beginning of Friday's class.
Work on the homework due Monday.
Tasks due Monday, October 19th:
Homework due:. Two integer are coprime if they share no prime factors. Your homework is to find a formula for the number of integers between 0 and n that are coprime to n. Hint: Do this by inclusion-exclusion. (There are other proofs, and you are welcome to come up with some other proof.) Don't go searching on the internet before you have come to me for hints as to how to construct the inclusion-exclusion proof, because it's so fun.
In class Friday we had this handout. Before class, please find two bijections between the different problems (they all have the same answer as counting problems). Might I suggest Mountains and Parentheses as a fairly easy one. You pick at least one other pair to come up with a bijection for.
Tasks due Wednesday, October 21st:
I didn't tell you anything, sorry.
Tasks due Friday, October 23rd:
I didn't tell you anything, sorry.
Tasks due Monday, October 26th:
We will continue the worksheet in class Monday, and I may give you some more fun problems. Monday will be our last generating function day.
Please read Chapter 8 as needed. It is full of examples and more detail than we will do on generating funtions, so focus on things that are familiar.
Tasks due Wednesday, October 28th (QUIZ):
Finish reading Chapter 8 and reviewing about generating functions.
Here are solutions to the worksheet on generating functions.
QUIZ: I would like you to be able to do things similar to what's on the worksheets we just did. Don't forget your binomial theorem, please. Please study the examples we did. I may even ask you to do an example we saw in course notes or on worksheets (an exact example you've seen). So your best approach to studying is to study these examples in detail.
Tasks due Friday, October 30th:
None. We will start graph theory today.
Tasks due Monday, November 2nd:
Keep thinking about how to prove the existence of an Eulerian circuit in a graph with all even degree; we'll finish this at the beginning of next class.
I recommend you start reading the Graph Theory chapter (chapter 9).
Finish reading the Graph Theory chapter (chapter 9). We are mostly skipping 9.3.
Note: in answer to a question in class, you can show that the degree bound of n/2 in the Hamiltonian theorem we did in class is optimal, by considering the bipartite graph on parts of size r and r+1.
Start reading the chapter about trees (chapter 10).
Do exercises in Chapter 9. I suggest Exercises 1, 5 (hint: pigeonhole), 6 (hint: use the Eulerian circuit), 7 (we did this, just remember it), 8, 10 (use Theorem 9.4; read the proof), 12.
Tasks due Monday, November 9th:
Homework (to hand in today): A graph is called 2-connected if one must remove at least two edges to make it disconnected. A) Show that a Hamiltonian graph (one with a Hamiltonian cycle) is necessarily 2-connected. B) Show that if G is 2-connected and does not have a subgraph of the form of the Claw Graph (click for picture), then it IS Hamiltonian. C) Show that if G is 2-connected and does not have any induced subgraphs of the form of the Claw Graph (click for picture) or the Triangle With Tail (four vertices; it is the first graph shown here), then it IS Hamiltonian. Hint: Work by contradiction; take the longest cycle in the graph, and then consider a nearby vertex it doesn't include.
Tasks due Wednesday, November 11th:
Read Chapter 10, up to and including 10.2.
Tasks due Friday, November 13th:
Read Chapter 10. We will finish Chapter 10 (including 10.4) today (probably).
Some suitable exercises from Chapter 10 are #2 (prove your conjecture), #4 (what's the maximum size of an isomorphism class?), #5 if you want something more involved, #6 (draw a picture of the function as arrows), #9, #10.
None. We'll start talking about graph colouring in class.
Tasks due Monday, November 30th:
We'll talk about graph colouring, and finish up graph theory.
Tasks due Wednesday, December 2nd:
We have a little bit of graph theory left (the marriage problem), and then we'll start Combinatorial Game Theory.
I'm going to spend the last few days of the semester on combinatorial game theory, in a very low-key and exploratory way. This will essentially `start the course over' again, and it will involve one homework assignment, due a week from today. (The classic texts for this are `On Numbers and Games' by Conway, and `Winning ways for your mathematical plays' by Berlekamp, Conway and Guy. We'll only cover the basics, and I will provide resources, so there is no need to buy the books.)
Tasks due Friday, December 4th:
We started combinatorial game theory.
Tasks due Monday, December 7th:
We will define the Surreal Numbers and continue combinatorial game theory.
There will be no more homework or quizzes in the class.
