## 2017-07-28

### Introduction to Enumerative, Algebraic, and Bijective Combinatorics (2016) by Xavier Viennot

# You can also click the upper-left icon to select videos from the playlist.

source: matsciencechannel     2016年1月6日
A course by Xavier Viennot
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 correspondance 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 correspondance, 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.
www.xavierviennot.org

Chapter 0: Introduction to the course 1:09:53
Chapter 1a: Ordinary generating functions 1:22:41
Chapter 1b: Ordinary Generating Functions 1:22:32
Chapter 1c: Ordinary Generating Functions 1:24:19
Chapter 1d: Ordinary Generating Functions 1:22:19
Chapter 2a: The Catalan Garden 1:20:51
Chapter 2b: The Catalan Garden 1:34:49
Chapter 2c: The Catalan Garden 1:21:22
Chapter 2d: The Catalan Garden 1:26:32
Chapter 3a: Exponential Structures and Exponential Generating Functions 1:17:09
Chapter 3b: Exponential structures and exponential generating functions 1:19:27
Chapter 4a: The n! garden 1:26:39
Chapter 4b: the n! garden 1:18:49
Chapter 4c: the n! garden 1:13:15
Chapter 4d: The n! garden 1:34:43
Chapter 5a: Tilings, Determinants, and non-crossing paths 1:14:06
Chapter 5b: Tilings, determinants, and non-crossing paths 1:35:24