S.V.Duzhin
Combinatorics
Until recently, combinatorics was thought of as an irregular collection
of beautiful isolated tricks.
The first serious attempt to lay the foundation of combinatorics as
a unified science was undertaken by Bergeron, Labelle and Leroux in their
book "Combinatorial Species and Tree-like Structures".
The book is dedicated to the exposition of combinatorics based on the
notion of a combinatorial species introduced by A.Joyal.
At first sight, the definition of a combinatorial species
looks trivial; however, as the narration of the three authors
goes on, you see that meaningful combinatorial constructions and
facts appear naturally out of nothing.
The present course covers the fundamentals of the theory of
combinatorial species as well as a certain related set of beautiful
isolated tricks of classical combinatorics.
Draft course program
1. Sequences and generating functions
o solution of linear recurrence relations
o numbers of Fibonacci, Catalan, Bernoulli, Euler
o algebra of formal power series
o asymptotic of coefficients
2. Introduction to the theory of species
o definition, examples
o power series associated with a species
o operations on species
o molecular and atomic species
o Lagrange inversion
3. Enumeration
o Burnside's lemma
o Polya's formula
o tree enumeration
o plethysm and Schur's functions
4. Partitions
o Young diagrams
o Euler's pentagonal theorem
o Glasher's and Sylvester's correspondences
o asymptotics of Hardy--Ramanujan
o Robinson--Shensted--Knuth correspondence
5. Partially ordered sets
o Moebius algebra
o Moebius function
o Moebius inversion
Literature
F.Bergeron, G.Labelle, P.Leroux "Th\'{e}orie des esp\`{e}ces et
combinatoire des structures arborescentes", Montr\'{e}al, 1994
(English translation: "Combinatorial Species and Tree-like Structures",
Cambridge University Press, 1998).
P.Cameron. Combinatorics. Cambridge, 1994.
R.Stanley. Enumerative combinatorics. éÚÄ. íÉÒ.
S.K.Lando. Combinatorics. MCCME, 1994 (in Russian)
(http://www.mccme.ru/ium/ancient/combs93.html).