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!
- Catalan paths
- Derivation of the Catalan recurrence
- Generating series, sum and product rules
- Explicit formula for the Catalan numbers
- Generating series
- 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
- To be continued…