Combinatorics

Combinatorics (Summer session 1, 2021) is the mathematics of finite or discrete objects. Frequently, and most classically, we are interested in counting the number of ways that a certain problem can be solved. For example, the number of ways of tiling a rectangle using rectangles and rectangles with no gaps or overlaps is the Fibonacci number , a very familiar sequence of numbers. Many other simple counting problems have answers that involve the binomial coefficients.

In this class, we will assume that students are already familiar with these basic combinatorial problems and their solutions so that we can study combinatorics at a higher level. After briefly reviewing combinatorics at the level of typical competition problems, we will look at other, less familiar, types of special numbers, such as the Stirling numbers, the Bell numbers, and the Eulerian numbers. These numbers satisfy relations resembling those of the binomial coefficients, but they also have their own distinctive characters. They show up in several different contexts in mathematics, from counting problems to polynomial identities, which suggests that they are fundamental objects in mathematics.

We will also study sieve methods, which allow us to count objects with only desirable properties. A very famous sieve method problem is the derangement problem, which asks for the number of ways that people can rearrange their hats so that everyone has the wrong hat. A less famous but still important sieve method problem asks, for a given subset of an board, how many ways are there to place rooks on so that no two are attacking. In fact, the derangement problem is a special case of this rook placement problem!

We will also investigate partially ordered sets. An ordering (or a total order) on a set is a way of taking any two elements and saying that either or . A partial ordering is a generalization that allows us to compare some pairs of elements while saying that other elements are incomparable. For example, the positive integers with divisibility is a partially ordered set: given two positive integers and , it might be the case that or , but it might be the case that neither one divides the other. Associated to any partially ordered set is a set of functions called the incidence algebra, each of which can be represented as a matrix. The incidence algebra captures all the combinatorial information about the poset in an easy-to-use form, and it contains elements which behave like the zeta function and Möbius function do for the integers.

Finally, we will study generating functions. The theory of generating functions is a very powerful way of solving combinatorial problems and investigating their asymptotics. Generating functions typically play well with recurrences: they make solving linear recurrences as easy as finding roots of polynomials, and we can also use them to come up with recurrences, giving rise to some spectacular consequences. For instance, there is a beautiful and completely explicit bijection between binary trees and 7-tuples of binary trees. This is not true if 7 is replaced by a smaller number, other than 1. Generating functions are also helpful in studying asymptotic combinatorics, where we might not care exactly how many solutions there are to a problem, but only an approximation given in terms of more familiar functions like polynomials and exponential functions.

Problem sets in this class will contain many possible exploratory research problems for interested students to work on.

This class will meet Monday, Tuesday, Thursday, and Friday mornings from 9:30–11:30 AM Pacific time for 5 weeks, starting June 7th. Applications are due April 25th. Click here to apply!