Introduction to Enumerative Combinatorics

Combinatorics is a branch of mathematics which deals with finite sets and their cardinalities. It is about counting certain objects having certain given properties. A typical question in combinatorics starts with the words "In how many ways" (we can do something).
"In how many ways can we split 100 in a sum of distinct positive integers?", as an example.

This online course is partially based on the course “Discrete Mathematics” for HSE bachelor students majoring in mathematics.

The first half of the course (lectures 1 to 4) will be devoted to basic principles of enumeration. We will encounter basic combinatorial notions such as permutations, binomial coefficioents, Fibonacci and Catalan numbers, etc.
In the second part of the course (lectures 4 to 8) we will be dealing with a very powerful method of solving combinatorial problems, namely generating functions. With their help we will study recurrence relations, partitions and variations of binomial coefficients -- the Gaussian binomial coefficients or q-binomial coefficients as they are sometimes called.

The course consists of an introduction and eight lectures -- a lecture per week. Each lecture lasts for 1h30m approximately and is split into several shorter parts. Weeks 1-3 and 5-7 contain a quiz, whereas weeks 4 and 8 end by peer-graded assignements -- midterm and final exams.

Do you have technical problems? Write to us: [email protected]

• Introduction
• Permutations and binomial coefficients
• In this introductory lecture we discuss fundamental combinatorial constructions: we will see how to compute the number of words of fixed length in a given alphabet, the number of permutations of a finite set and the number of subsets with a given number of elements in a finite set. The latter numbers are called binomial coefficients; we will see how they appear in various combinatorial problems in this and forthcoming lectures. As an application of combinatorial methods, we also give a combinatorial proof of Fermat's little theorem.
• Binomial coefficients, continued. Inclusion and exclusion formula.
• In the first part of this lecture we will see more applications of binomial coefficients, in particular, their appearance in counting multisets. The second part is devoted to the principle of inclusion and exclusion: a technique which allows us to find the number of elements in the union of several sets, given the cardinalities of all of their intersections. We discuss its applications to various combinatorial problem, including the computation of the number of permutations without fixed points (the derangement problem).
• Linear recurrences. The Fibonacci sequence
• We start with a well-known "rabbit problem", which dates back to Fibonacci. Using the Fibonacci sequence as our main example, we discuss a general method of solving linear recurrences with constant coefficients.
• A nonlinear recurrence: many faces of Catalan numbers
• In this lecture we introduce Catalan numbers and discuss several ways to define them: via triangulations of a polygon, Dyck paths and binary trees. We also prove an explicit formula for Catalan numbers.
• Generating functions: a unified approach to combinatorial problems. Solving linear recurrences
• We introduce the central notion of our course, the notion of a generating function. We start with studying properties of formal power series and then apply the machinery of generating functions to solving linear recurrence relations.
• Generating functions, continued. Generating function of the Catalan sequence
• In this lecture we discuss further properties of formal power series. In particular, we prove an analogue of the binomial theorem for an arbitrary rational exponent. We apply this technique to computing the generating function of the sequence of Catalan numbers.
• Partitions. Euler’s generating function for partitions and pentagonal formula
• In this lecture we introduce partitions, i.e. the number of ways to present a given integer as a sum of ordered integer summands. There is no closed formula for the number of partitions; however, it is possible to compute their generating function. We study the properties of this generating function, including the famous Pentagonal theorem, due to Leonhard Euler.
• Gaussian binomial coefficients. “Quantum” versions of combinatorial identities
• Our final lecture is devoted to the so-called "q-analogues" of various combinatorial notions and identities. As a general principle, we replace identities with numbers by identities with polynomials in a certain variable, usually denoted by q, that return the original statement as q tends to 1. This approach turns out to be extremely useful in various branches of mathematics, from number theory to representation theory.