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.
  1. Binomial coefficients and q-binmoial coefficients.
  2. Generating functions.
  3. Linear recursion.
  4. Catalan numbers.
  5. Bernoulli–Euler numbers,
  6. Permutations and compositions.
  7. Trees and Lagrange inversion.
  8. Parking functions.
  9. Partially ordered sets and the Moebius inversion.
  10. Tutte polynomial of a graph.
  11. Euler's pentagonal identity.

Textbooks

  1. S.Lando, Lectures on Generating Functions, AMS, 2003.
  2. G.Andrews, The Theory of Partitions, Cambridge University Press, 1998.

Lectures

  1. Binomial coefficients.
  2. Linear recursion I: generating functions.
  3. Linear recursion II: explicit formulas.
  4. Lattice paths and Catalan numbers.
  5. Binomial series, exponentials and logarithms.
  6. Trees: elemenraty facts and the Pruefer code.
  7. Trees: Lambert function.
  8. Parking functions.

Rambler's Top100