CoursE  X.V.  IMSc  2016  


Course  IMSc  Chennai, India 

January-March 2016

An introduction to enumerative, algebraic and

bijective combinatorics

  Tuesday and Thursday  14h-15h30 

Alladi Ramakrishnan Hall


A spectacular renaissance is appearing for combinatorial mathematics. One of the first step is the resolution of enumerative problems. Very often motivations come from other fields such as theoretical physics (statistical and quantum physics), probabilities theory, algebraic geometry, analysis of algorithms in computer science or molecular biology. The main tool is the notion of generating power series (ordinary and exponential). Recurrence formulae, functional or differential equations, inversion formulae, rational, algebraic or D-finite power series appear everywhere in this domain called enumerative combinatorics.

Another trends appearing is the « bijective paradigm ». A bijective proof of an identity will be the construction of a correspondence between the finite objects interpreting both sides of the identity. Conversely, it can be the search for combinatorial interpretations of objects or topics from some parts of classical mathematics (algebra, analysis, algebraic geometry, ….). The interplay between algebra and combinatorics is called algebraic combinatorics. Very recently bijective combinatorics has played an important role in theoretical physics (combinatorial maps in quantum gravity, resolution of the Razumov-Stroganov conjecture, …).

More generally « bijective tools » enables to put some order in the jungle of combinatorial identities. For example, many enumeration formulae involving determinants can be proved using a single Lemma relating determinants and configurations of non-intersecting paths. 

In this course topics will include ordinary and exponential generating series, the main bijections related to the Catalan world (trees, paths, triangulations, ….) and to the n! world (permutations, Young tableaux, Robinson-Schensted correspondence, Laguerre histories), determinants and non-crossing paths, tilings, combinatorial theory of differential equations.

This course is supposed to be the first of a series of 3 or 4 combinatorics courses, with emphasis on the bijective point of view. Other courses will be about a combinatorial theory of orthogonal polynomials, heaps of pieces in interaction with physics and algebra, and the « cellular ansatz », that is the interplay between quadratic algebras and combinatorics.

Ch 0  Introduction to the course

    5 January 2016

                               slides     (pdf   25 Mo)             video Ch 0       (1h 10mn)

enumerative combinatorics 3   50’‘    video

an example with Young tableaux 5  2’  8’‘   video

Hook-length formula 10  6’  12’’  video

another example with binary trees, the use of ordinary generating functions  19   9’  34’’  video

an example with alternating permutations, the use of exponential generating functions 35  17’  5’’  video

bijective combinatorics, example: planar maps 42  29’  35’’  video

bijective proof of an identity, example RSK  48   35’  10’‘    video

algebraic combinatorics 55   39’  50’‘   video

the bijective paradigm 62  43’  55’‘   video

example: Mehler identity for Hermite polynomials 64    45’  20’‘   video

Identities, bijections, « bijective tools »  84   55’  41’’  video

example: hook-length formula and number of tilings of the  Aztec diagram under the same roof 89  59’  33’‘   video

another example: heaps of pieces 95  1h  4’  11’‘   video

map of the course 97  1h  5’  31’’  video

other courses    98    1h  8’  50’‘    video

the end 98    1h  9’  52’‘ 

    the  playlist from matsciencechannel of the 17 videos of the course is   here

last update: 16  April 2016

return to:

courses  website

main Xavier Viennot  website