Math 3152b -- Combinatorial mathematics

Instructor	Graham Denham
Office hours	TBA
Class times	TuTh 12:00-13:20.
Class location	MC 108
Textbook	Generatingfunctionology, by Herbert Wilf, 2nd edition freely available as a pdf.
Prerequisites	0.5 course from: Mathematics 2120A/B, 2156A/B, 2211A/B, Applied Mathematics 2811B or the former Mathematics 203b, or permission of the Department.
Midterm exam date	February 16 (in class)
Final exam	see below
Evaluation	40% Final exam; 30% midterm; 30% assignments

Assignments

Learning the art of counting requires, above all, practice.  Accordingly, there will be regular homework assignments.  This is the most important part of the course.  Please note that no late assignments will be accepted.  Assignments will be posted here.

• Assignment 1, due 24 Jan at the start of class.
• Assignment 2, due 9 Feb (at the start of class!) Solutions.
• Assignment 3, due 6 March (at the start of class).  
• Assignment 4, due 22 March.  Solutions.
• Assignment 5, due 12 April. Solutions.
  

Some of the assignment problems will be routine, and some will take some thought.  Collaborating with other people can add a lot to the experience of doing math, and I encourage you to do so.  (Research-level mathematics can be done alone, but is probably more often done in groups of two or three.)  Just make sure to write your own solutions, your own way, and to acknowledge any debts you may have.  Ask me if in doubt.

Sometimes it can be useful to use some symbolic computation software, for example to evaluate a few terms of a power series.  Try Maple or Mathematica, if you have access or familarity.  You can also use Sage, an open-source symbolic computation tool, online and for free.  For example, create a Sage notebook, and enter the following:
This will give you the first ten terms of the exponential generating function for the Bell numbers.

Reading

The main reference will be Wilf's book on combinatorics of generating functions, the second edition of which is freely available (see above).  The book Introductory Combinatorics  by Richard Brualdi is also good reading for some of the topics in the course.

Synopsis

Here is some attempt to keep track of what we have actually been doing in class.

• 1/19: review of counting permutations and combinations of sets and multisets
  
• 1/24: algebra of formal power series: sums, products, reciprocals, composition
• 1/26: counting with ordinary generating functions: five constructions from Chapter 2
• 1/31: counting with ordinary generating functions (continued): we considered products of ogf's in detail, and counted the number of partitions using the amazing infinite product \[\sum_{n=0}^\infty P(n)t^n=\prod_{n\geq1} (1-t^n)^{-1}.\]  We reviewed the generalized binomial theorem.
  
• 2/2: the Catalan numbers as a solution to 5 counting problems.  We saw they were determined by the recurrence relation \(C_0=1\), \[C_{n+1}=\sum_{k=0}^n C_kC_{n-k}.\]  This gave a recipe for their ordinary generating function, \(F(t)=\frac{1-\sqrt{1-4t}}{2t}\), which led to the expression \[C_n=\frac{1}{n+1}{2n \choose n},\] for all \(n\geq 0\).
• 2/7: counting with exponential generating functions (Chapter 2).  A quick review of how to solve linear, homogeneous differential equations.
• 2/9: exploiting multiplication of exponential generating functions.  E.g., the number of \(1\times n\) strips of squares coloured red, green and blue, with at least one green and an even number of reds, has exponential generating function \[\frac{e^x+e^{-x}}{2}(e^x-1)e^x.\]  Introduction to Dirichlet generating functions.
• 2/14: more on formal Dirichlet series.  We saw that if \(f(n)\) is a multiplicative function, then \[\sum_{n\geq1}f(n)/n^s = \prod_{p}\sum_{k\geq0}f(p^k)/p^{ks}.\] This had various interesting special cases and, in particular, led to the Moebius inversion formula.  One application: the \(n\)th cyclotomic polynomial is given by the expression \[\Phi_n(z)=\prod_{k|n}(z^k-1)^{\mu(n/k)}.\]
• 2/16: midterm
• 2/21, 2/23: break
• 2/28: ordinary and exponential generating functions for Stirling numbers of the second kind.  An exponential generating function for the Bell numbers: \(\sum_{n=0}^\infty b(n)t^n/n! = e^{e^t-1}\).
• 3/1: more about permutations: inversion sequences.  Here are some notes on inversions.
• 3/6: exponential families.  We saw the Stirling numbers of the first kind satisfied the egf formula \[\sum_{n,k\geq0} c(n,k)\frac{t^n}{n!}u^k = (1-t)^{-u}.\]
• 3/8: exponential families, continued.  The exponential formula (Chapter 3.)
• 3/13: counting examples: labelled graphs, labelled trees, and set partitions with restrictions on the sizes or numbers of parts.
• 3/15: still more examples.  In an exponential family, we saw that the number of ordered hands is counted by \[\frac{1}{1-yD(x)},\] where \(D(x)\) is the deck generating function.
• 3/20: unlabelled counting, using ordinary generating functions.  This time, if the number of cards of weight \(r\) was equal to \(d_r\), the number of hands \(h(n,k)\) with \(k\) cards and weight \(n\) satisfied the equality \[\sum_{n,k}h(n,k)x^ny^k=\frac{1}{(1-x^ry)^{d_r}}.\]
• 3/22: examples: solutions to linear, diophantine equations (a.k.a. counting combinations of a multiset.)  In particular, we found an expression for the greatest integer which could not be expressed as a nonnegative integer linear combination of numbers \((a_1,a_2)\), provided these numbers were relatively prime.
• 3/27: class cancelled, sorry.  For practice, you might want to do some more labelled and unlabelled counting problems.
• 3/29: we completed the theory of decks and hands: the number of ordered hands in a prefab is counted by \[\frac{1}{1-yD(x)},\] where \(D(x)\) is the (ordinary) deck generating function.  Application: \(2\times n\) and \(3\times n\) domino tilings could be viewed as ordered hands.  We found the ogfs for each of those rather quickly using this approach.
• 4/3: counting with symmetry: Burnside's lemma for counting colourings up to symmetry.
• 4/5: counting with symmetry: the cycle indicator polynomial
  

Syllabus

This is an intermediate course in enumerative combinatorics, the study of counting.  We will review the basics -- how to count permutations and combinations of labelled and unlabelled objects.  We will see how to use formal power series (also known
as generating functions) to solve counting problems easily and systematically.  Topics include:

• permutations and combinations of sets and multisets
• introducing formal power series
• ordinary and exponential generating functions
• solving recurrence relations
• counting graphs and trees
• Joyal's theory of species
• counting in the presence of symmetry (Polya theory) or Lagrange inversion

Exams

We will have a Midterm on February 16 in class.  Here are some solutions.  The Final Exam will be a take-home exam: arrange with me to pick it up between April 12th and 19th, (or later; just ask me about it) and return it 24 hours later.  (Note: the exam should take you 3 hours, not 24!)

---

Postal Address

Department of Mathematics
Middlesex College
University of Western Ontario
London, ON N6A 5B7
Canada

Contact

Email:
Phone:	+1 519 661 2111 x86527
Office:	MC 135

Content

• Home
• Publications
• Teaching
• Other

Research | Teaching | Other | Back to top © 2012 Graham Denham | original design by Andreas Viklund