Introduction to combinatorics
Lector Yu.Burman
Combinatorics is a part of mathematics dealing with finite sets to answer
the question «how many?». Combinatorics may be regarded as a
focal point of the whole course of mathematics. From one side, combinatorics
makes use of a variety of methods taken from all possible parts of
mathematics, from linear algebra to probability theory to Euclidean geometry.
From the other side, combinatorial methods and a combinatorial way of
thinking are indispensable in studying of the more advanced courses, such as
algebraic geometry, representation theory or mathematical physics. So
combinatorics is a must for every mathematician.
Prerequisites
The methods of combinatorics are versatile, so the more erudite a student is
the better is he/she ready for this course. Elementary linear algebra is
definitely required.
Syllabus
The syllabus below is subject to change depending on the students' progress.
- Binomial coefficients and q-binmoial coefficients.
- Generating functions.
- Linear recursion.
- Catalan numbers.
- Bernoulli–Euler numbers,
- Permutations and compositions.
- Trees and Lagrange inversion.
- Parking functions.
- Partially ordered sets and the Moebius inversion.
- Tutte polynomial of a graph.
- Euler's pentagonal identity.
Textbooks
- S.Lando, Lectures on Generating Functions, AMS, 2003.
- G.Andrews, The Theory of Partitions, Cambridge University Press, 1998.
Lectures
- Binomial coefficients.
- Linear recursion I:
generating functions.
- Linear recursion II:
explicit formulas.
- Lattice paths and Catalan
numbers.
- Binomial series, exponentials
and logarithms.
- Trees: elemenraty facts and the
Pruefer code.
- Trees: Lambert function.
- Parking functions.