XAVIER VIENNOT
  • PART I
    • abstract
    • contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • list of bijections
    • index
  • PART II
    • abstract
    • contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Some lectures related to the course
  • PART III
    • abstract
    • contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • references, comments and historical notes
  • PART IV
    • introduction
    • contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • references
  • Epilogue

The Art of Bijective Combinatorics   Part I 

An introduction to enumerative, algebraic and bijective combinatorics

 

The Institute of Mathematical Sciences, Chennai, India  (January-March 2016)

Abstract

 

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.

 

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