Introduction to Enumerative Combinatorics

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.

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).

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.

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.