Instructor | Graham Denham |
---|---|

Office hours | WF, 2:30-3:30pm |

Class times | MWF 11:30-12:30pm |

Class location | MC 107 |

Textbook | Introductory Combinatorics, 5th edition, Richard Brualdi, available at the bookstore |

Prerequisites | 0.5 course from: Mathematics 2120A/B, 2155A/B, 2211A/B, Applied Mathematics 2811B, or permission of the Department. |

Midterm exam date |
October 25 and 27 (two parts; in class) |

Final exam | December 16th, 9am-noon; HSB 11. |

Evaluation | 40% Final exam; 30% midterm; 30% assignments |

- 9-8: Introduction and overview. Our focus will be mostly on counting. What, though, constitutes a solution to a counting problem?
- 9-11, 9-13, 9-15: permutations and combinations. We can organize some classical counting problems in terms of additive and multiplicative principles. \(k\)-element sequences of entries from \([n]=\{1,2,...,n\}\) can also be thought of as functions \(f\colon[k]\to [n]\). From this point of view permutations are the injective functions. The discussion extends to permutations of multisets, which we see can be counted by multinomial coefficients. Subsets of \([n]\) are in one-to-one correspondence with permutations of a multiset with just two kinds of element. This gets us back to classical binomial coefficients.
- 9-18: the pigeonhole principle 9-20: fancy variations and applications like the Erdos-Szekeres Theorem
- 9-22: generating permutations: the Johnson-Trotter algorithm.
- 9-25: finding your place in the Johnson-Trotter order. Inversions in permutations: recovering a permutation from its inversion sequence.
- 9-27: enumerating subsets: we looked at subsets of \([n]\) as n-digit binary sequences. By writing subsets as "words" with digits in decreasing order, we saw that the counting order and the lexicographic order were the same.
- 9-29: Gray codes and enumerating subsets of a fixed size.
- 10-2: if we express a subset of \([n]\) as a word by writing the
elements in decreasing order, then the counting order agrees with the
lexicographic order. If we restrict our attention to subsets of a
fixed size, we saw that it's fairly easy to say where, in order, a
given subset appears: if \(\{a_1,a_2,\ldots,a_r\}\) is a subset and
\(a_r>a_{r-1}>\cdots>a_1\), then the number of subsets that
comes before this one in order equals

\[{a_r-1\choose r}+{a_{r-1}-1\choose r-1}+\cdots+{a_2-1\choose 2}+{a_1-1\choose 1}.\]

A recommended exercise is to see what happens to this order if we try some variations: for example:

- write subsets as words in increasing order instead;
- reverse the "alphabetical order" by declaring larger numbers come before smaller numbers instead;
- replace subsets by their complements;
- consider the counting order in reverse.

- 10-4: properties of binomial coefficients: they count something, they are defined by a recurrence relation, and we can find identities that they satisfy, either by combinatorial or algebraic means.
- 10-6: Binomial coefficients are log-concave. Newton's binomial theorem, and the multinomial theorem.
- 10-16: the Principle of Inclusion-Exclusion allows us to count (finite) sets determined by overlapping conditions.
- 10-18: more examples of the P.I.E., including counting subsets of a multiset, and derangements.
- 10-20: asymptotics of derangements, and permutations with no consecutive \(i,i+1\)'s.
- 10-23, 25, 27: review and midterm
- 10-30: generating functions: the idea that a sequence indexed by nonnegative integers can be packaged and treated as a single object. We see that the various instances of the binomial theorem are already examples.
- 11-1: one can use (ordinary) generating functions to solve linear
recurrence relations. Products of sums of the form
\(1+t+t^2+\cdots+t^{a_i}\) give generating functions for the number of
combinations of a multiset \(\{a_1\cdot 1, a_2\cdot 2, \ldots, a_n\cdot
n\}\).

- 11-3: the expansion of \(1/(1-(X+Y+Z))\) can be viewed as a
formal sum of all words made from the symbols \(X\), \(Y\), \(Z\), and
more generally. This sometimes lets us write down a generating
function to solve a counting problem directly.

- 11-6,
8: exponential generating functions. Products of exponential
generating functions have a nice interpretation. We can count
"words" in a set of letters with various conditions on the number of
each letter by multiplying e.g.f.s.

- 11-10: composition of exponential generating functions. One place to read more about exponential generating functions is sections 3.1-3.5 of the book by Herbert Wilf, linked above.
- 11-13, 15: Catalan numbers turn out to be the solution to an
amazing number of equivalent counting problems. They satisfy a
quadratic recurrence relation that lets us compute the explicit formula
\(C_n=\frac{1}{n+1}{2n\choose n}\).

- 11-17: Stirling numbers of the second kind \(S(n,k)\) count the number of partitions of \([n]\) into \(k\) nonempty, unordered blocks. They satisfy a Pascal's-triangle-type recurrence relation, and the generating function \[\sum_{k,n\geq0}S(n,k)t^k x^n/n!\] simplifies beautifully.
- 11-20, 22: (Unsigned) Stirling numbers of the first kind \(s(n,k)\) count the number of permutations of \([n]\) with exactly \(k\) cycles. They also satisfy a Pascal's-triangle-type recurrence relation and have a nice generating function, as well as an inverse relationship with the \(S(n,k)\)'s.
- 11-24: The Eulerian number \(e_{n,k}\) is the number of permutations of \([n]\) with exactly \(k-1\) descents. The Eulerian numbers satisfy a fourth Pascal's-triangle-type recurrence relation. The Eulerian polynomials \(A_n(t)\) satisfy the formula \[\sum_{k\geq}k^nt^k=\frac{A_n(t)}{(1-t)^{n+1}}.\]
- 11-24,27: If \(p_n\) denotes the number of partitions of an integer \(n\), we find \[\sum_{n\geq0}p_nt^n=\prod_{k\geq 1}(1-t^k)^{-1}.\] Discussing this generating function leads to Euler's Pentagonal Numbers Theorem.
- 11-29: permutation groups
- 12-1: cycle types, orbits, stabilizers all leading up to Burnside's Lemma
- 12-4: applications of Burnside's Lemma to counting colourings up to symmetry (textbook, 14.2)
- 12-6: Pólya theory (textbook, 14.3) refines Burnside's Lemma to count colourings up to symmetry, keeping track of the number of times each colour appears.

- the pigeonhole principle

- 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

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, since presenting the work of others as your own constitutes a serious academic offence.

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:

var('t')

f = e^(e^t-1)

f.taylor(t,0,10)

f = e^(e^t-1)

f.taylor(t,0,10)

This will give you the first ten terms of the exponential generating function for the Bell numbers, which we will learn about in early November.

**Academic dishonesty:**
Scholastic offences are taken seriously and students are directed to read the official policy.

**Accessibility Statement:**
Please contact the course instructor if you require material in an
alternate format or if you require any other arrangements to make this
course
more accessible to you. You may also wish to contact Services for
Students with Disabilities (SSD) at 661-2111 ext. 82147
for any specific question regarding an accommodation.

**Support Services:**
Learning-skills counsellors at the Student Development Centre
are ready to help you improve your learning skills.
Students who are in emotional/mental distress should refer to
Mental Health@Western
for a complete list of options about how to obtain help.
Additional student-run support services are offered by the
USC.
The website for Registrarial Services is
http://www.registrar.uwo.ca.

**Eligibility:**
You are responsible for ensuring that you have successfully completed
all course prerequisites and that you have not taken an antirequisite
course.
Unless you have either the requisites for this course or written special permission
from your Dean to enroll in it, you may be removed from this course and it will be
deleted from your record. This decision may not be appealed. You will receive
no adjustment to your fees in the event that you are dropped from a course for
failing to have the necessary prerequisites.