MATH 249 (combinatorics, by the way) is a pretty interesting course. As much as I despise numbers, they are useful for certain things. Analysis immediately comes to mind, but in this post I’m going to talk about counting things. Don’t be afraid, I’m talking about nice sets. *Finite* sets. Maybe bijections, cardinals, and all that stuff will come up at another time.

There are two halves to MATH 249: enumeration, and graph theory. The midterm is in early March, and so far we’re still doing enumeration. It may sound ridiculous that anyone could spend 2 months discussing strategies for counting things, but it turns out that there are many questions that admit no straightforward solution.

In this course we’ve done things like the Fibonacci numbers, Catalan numbers, recurrences, ways of writing numbers as sums, and so on. A lot of this stuff really reminds you of things you’d see on a math contest. The assignments are interesting – I’ve found them pretty straightforward for the most part except for some stuff on string conjugacy that appeared earlier in the term. The connections are everywhere though. I can’t even count the number of times I’ve read a problem and thought about it for a while and then realized: “Wait a second, this is completely isomorphic to the Catalan path problem.” Seeing those innate connections between seemingly unrelated problems is part of what makes mathematics so beautiful to me. I mean, even a computer scientist has a reason to care about Catalan numbers: parenthesis matching, for example!

- Basics
- Number of permutations of
- Number of -subsets of
- Binomial coefficients and generalizations beyond integers via recursive definition
- Binomial theorem and its simple proof by induction
- Permutations and inversion sequences (bijection)
- -factorials, -binomial coefficients

- Catalan paths
- Derivation of the Catalan recurrence
- Generating series, sum and product rules
- Explicit formula for the Catalan numbers

- Generating series
- The purpose of generating series and what they represent
- Laurent series with coefficients from a ring
- The field of Laurent series over a field, and the necessary condition for the invertibility of power series
- The inverse of (geometric series formula)

- Formal languages
- Alphabets and languages: union, concatenation, star
- Weight functions; generating series of a language
- Decompositions of languages; equations relating languages
- Compositions of integers
- Obtaining recurrences from rational generating series
- Explicit formulas for and the use of partial fractions
- Probability generating series and word games

- Partitions of an integer
- Partitions of an integer; infinite product as a generating series
- Ferrers diagrams; self-conjugate partitions
- Extracting coefficients from certain infinite products

- -theory
- To be continued…

Hey, how hard is math 249?? I’m currently enrolled in 239 for the fall the term but I’m considering switching to 249 and that’s how I came across this blog. I’ve never taken an advanced math course before but I have done very well in the regular maths (math 130s, especially calculus 1 and 2). Am I gonna get owned since I’ve never taken any of the math 140 courses? What do you need to do to be successful in 249?

You can try 249, but it’s a tough course, and even worse if you’re not used to theoretical math, since that’s what the entire course is: proofs. The beginning of the course (enumeration) is quite easy but once he starts talking about integer partitions, q-theory etc. this is when things get difficult. The second half is graph theory, and from my experience graph theory proofs require more-than-average amounts of insight and creativity. If you’re interested in what the lectures will be like, see Professor Chris Godsil’s notes: http://quoll.uwaterloo.ca/math249web/pdfs/enum.pdf

Sorry if my response seemed discouraging as I didn’t mean it that way. If you feel like the material in those notes would be accessible to you then it probably will be, but it should be noted that advanced math is *nothing* like regular math; even if you have high 90s in all of those courses it usually still doesn’t tell you much about how you’d do in the advanced sections. Anyway, my advice is to sit in on the lectures; you’ll know rather quickly whether it’s what you want (last Fall, after the first week or two, about 50-75% of people disappeared from the math14x lectures).

The consensus among students seems to be that Math245/Math249 are pretty much the toughest advanced courses (relative to 145, 146, 147, 148), and I agree with this (more or less).

Thanks, I appreciate the informative and detailed response. I read through the first few sections of the lecture notes and while interesting, it does seem very challenging. I can’t say that coming up with proofs are what I’m best at either. Maybe I’ll stay in 239 for now and sit in on the first couple lectures for 249 once the term starts. I’d still like to try at least once advanced-level course though, (never got the chance to take 145, 147 etc. since I was originally in the faculty of arts before transferring to math). What do you know about stats 240?

Yeah, that sounds like a good idea. Usually it’s pretty rare that you can just jump into a second-year advanced course if you haven’t already been through at least one of the first-year advanced courses. In the first-year ones, they kind of allow you to pick up some “foundations” stuff – just various concepts that arise all the time in pure math-ish courses but probably aren’t seen too often in regular level courses. For example, understanding properly how second-order logic works, as well as the different methods of proof, is indispensable really.

Even if you’ve seen all the material before, you’d probably still be learning a lot, because of the theoretical standpoint from which they teach it. As an example, I took MATH 137 when I was a Science major in 2009 and got near-perfect, but last Fall (after my transfer to math) I decided to take 147. Despite “already knowing” single variable calculus, 147 was still *very* enlightening to me.

The story for Statistics is different, because there are no STAT courses taught in first year. I heard from one person that STAT 240 is made artificially difficult by the fact that the instructor usually assumes you’re in STAT 240 because you already know a fair bit of probability, and hence they just throw really challenging problems at you, while “skimping out” on actually teaching the material thoroughly. This is not at all what the rest of the advanced courses are like.

STAT 241, on the other hand, I’ve heard is quite good. I didn’t get the chance to take Prob or Stat in advanced-level sadly, since they didn’t line up with my schedule properly. Anyways, your situation seems a little awkward since it’s a little late in the game, but my suggestions would be:

1) just take one of the first-year advanced courses; if you can complete one of these courses successfully then you’ll probably be well-prepared for 249 or further pure math courses

2) spend some time between now and Fall learning about the things I talked about, developing proof-writing skills, etc. and then 249 should be within reach.

Hope this helps! Good luck!

How hard is math 249 relative to USAMO/IMO problems?

Hello! Any chance you still have a copy of Godsil’s notes that you linked to in the comment thread above? The link has since been taken down. I am taking 249 with him this term and was hoping to get some preemptive studying done.

I’ve updated the link, but the notes are posted on his website.

Hi mlbaker, what are your thoughts on auditing 239 and taking math 247 in one term then taking 249 the next. I have not taken any advanced classes but the course looks intresting.