• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • 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
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • 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
    • Lectures related to the course
  • PART III
    • Preface
    • 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
    • Preface
    • 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)

Ch 1  Ordinary  generating  functions        
Ch 1a

7 January 2016
slides Ch1a     (pdf    26  Mo)        
video Ch1a  link to YouTube   (1h 22mn)
video Ch1a  link to bilibili
an example: binary trees    slide: 3      25
        Euler triangulations  13      6:24
intuitive introduction to ordinary generating functions and formal power series  17      9:45
        a little exercise: Fibonacci generating function  23     11:11
formal power series algebra: formalisation 29     13:24
        algebra of formal power series  33    15:25
        summable family  35    18:13
        infinite product  38    20:45
        other  operations 40     22:12
        free monoid and non-commutative power series  44    28:05
operations on combinatorial objects, intuitive introduction with binary trees  47    32:10
operations on combinatorial objects, formalisation 55     37:31
        sum 59     47:12
        product  60      48:23
        sequences  61    50:00
operations on combinatorial objects, example: integer partitions, q-series  63     51:28
        generating function for (integer) partitions  73     58:39
        execrcise:  D-partitions  74     59:50
Rogers-Ramanujan identities  76     1:02:54
bijective proof of an identities  82     1:08:21
visual proof:Pythagore  84     1:09:01
bijective proof of an identity, the bijective paradigm 112     1:10:12
bijective combinatorics, example: Catalan numbers  126     1:14:15
Dyck paths  133      1:19:07
the end 139    1:22:40

Ch 1b

12 January 2016
slides Ch1b     (pdf    20  Mo)        
video Ch1b  link to YouTube (1h 22mn)
video Ch1b  link to bilibili
from the previous lecture   slide:3       0:05
operation on combinatorial objects, derivative 16     4:45
operation on combinatorial objects, derivative, example: heaps of dimers 20    10:58
        heaps of dimers: definition  21    11:22
        the logarithmic lemma for heaps of dimers     18:40
        pyramid and maximal piece: definition    19:24
proof of the logarithmic lemma for heaps of dimers  28     22:30
exercises:  pyramids and algebraic generating functions  37    29:56
        semi-pyramids of dimers  38      30:07
        pyramids of dimers  41    32:17
        bilateral Dyck paths  42     34:07
operation on combinatorial objects, substitution, example:  Strahler number of a binary tree  44     37:49
        substitution  45     38:26
        Strahler number of a binary tree: definition  47     42:00
        Hydrogeology  49-51     44:37
        functional equation for two variables generating function of Strahler number  52     47:19
        experimental combinatorics  53-59      50:02
        Pascal, Pingala and Fibonacci  60      55:34
        substitution in binary trees  65-72      58:21
generating functions: rational, algebraic, D-finite  76     1:05:05
rational generating functions  79      1:09:13
        weighted paths  81      1:09:45
        self-avoiding path and circuit 83     1:11:48
        elementary circuit and cycles  84    1:12:24
        main proposition: generating function for weighted paths in a graph as  N_(i,j)/D  86    1:13:47
        linear algebra proof of the main proposition  87-91     1:18:25
the end 92     1:22:31

Ch 1c

14  January  2016
slides Ch1c     (pdf   20  Mo)        
video Ch1c  link to YouTube (1h 24mn)
video Ch1c  link to bilibili
from the previous lecture    slide: 3      15’‘  
bijective proof of the identity  N_(i,j)/D  9     3’ 09’‘   
        construction of the involution  phi  12    9’ 49’‘ 
an example and an exercise for N_(i,j/)D  19     25’ 30’‘
        an example: paths on a graph with 2 vertices  20     25’ 36’‘ 
        exercise: directed path  21  28’ 24’‘
another example for N_(i,j)/D: bounded Dyck paths  23     32’ 03’‘ 
        Fibonacci polynomials and matchings  30      36’ 31’‘
Fibonacci polynomials  34     39’ 55’‘
        generating functions for Fibonacci polynomials  37     40’ 30’‘
        exercise: coefficient of the Fibonacci polynomials 39       45’ 38’‘
        Pingala and Fibonacci  40-41      46’ 18’‘
exercise: Fibonacci numbers and polyominoes  42      49’ 02’‘
Fibonacci and Tchebychef polynomials  44      53’ 08’‘
Lucas and Tchebychef polynomials  50     59’ 25’‘
        exercise: relation Fibonacci and Lucas polynomials  55      1h 3’ 10’‘
complement: matching polynomial of a graph  56      1h 3’ 45’‘
        zeros of the matching polynomial of a graph 60     1h 5’ 53’‘
        exercise: coefficients of the Hermite and Laguerre polynomials  63  1h 8’ 40’‘   video
example of  N_(i,j)/D, back to Strahler number  64  1h 8’ 58’’
        logarithmic height of a Dyck path  68  1h 9’ 58’‘       
        generating function for Strahler  numbers  74      1h 16’ 08’‘
exercise, proof by killing involution: Euler’s pentagonal theorem  76     1h 17’ 55’‘
the end  81     1h 24’18’’

Ch 1d

19  January 2016
slides Ch1d    (pdf  24 Mo)          
video Ch1d  link to YouTube (1h 22mn)
video Ch1d  link to bilibili      
from the previous lecture, proof of the Euler’s pentagonal theorem      slide 3     15’‘
 another exercise with a sign reversing involution
      (generating function for heaps of dimers on a segment)  14      10’ 35’‘
more about rational series  16     12’ 57’‘
        zeros of Fibonacci polynomials  19      17’ 30’‘
        zeros of Lucas polynomials  20     18’ 40’‘
Lagrange inversion formula  21    19’ 01’‘
algebraicity with hidden decomposable structures, example: planar maps  25     26’ 36’‘ 
        system of equations for rooted planar maps and the bijection Cori-Vauquelin 31     32’ 03’‘
        direct formula for the number of rooted planar maps  33     34’ 18’‘ 
        blossoming trees and idea of Schaeffer bijection  37     36’ 21’’
complements:  algebraicity with hidden decomposable structures, example: directed animals  41     38’ 35’’ 
        system of equations for directed animals  44     40’ 57’’
        exercise: system of equations for prefix of Motzkin paths 45     41’ 25’‘
        random directed animals  47-48     45’ 49’‘
an anecdote  (about directed animals)  49     46’ 18’‘
complements: algebraicity with hidden decomposable structures, example: convex polyominoes  54     49’ 31’’
        exercise: directed and vertically convex polyominoes  59     50’ 22’‘ 
        formula for the number of convex polyominoes with given perimeter  64     52’ 50’‘
        random convex polyominoes  (with fixed perimeter)  66     53’ 31’‘
        random convex polyominoes (with fixed area)  67-68     54’ 17’‘
rational and algebraic generating functions, a flavor of theoretical computer science,
        Schützenberger’s methodology coding with words of algebraic languages  69     54’ 51’‘
        algebraic language and algebraic grammar  70  55’ 22’’
        non-ambiguous grammar for the Dyck language, derivation tree  73     1h 3’ 05’‘
        Chomsky-Schützenberger theorem  75     1h 5’ 29’‘ 
        algebraic equation for prefix of Motzkin paths  76    1h 9’ 54’‘
        automaton and rational language  77     1h 10’ 09’‘
generating functions, algebraic, D-finite or not D-finite ?  81     1h 15’ 26’‘
        paths in a quadrant  83     1h 16’ 16’’
        Kreweras and Gessel paths  84     1h 17’ 29’‘
        catalytic variables and kernel methodology 85     1h 18’ 12’‘
        the queen     1h 20’ 45’‘ 
        an example of generating function not D-finite: connected heaps of dimers 87    1h 21’ 25’‘
the end  88  1h 22’ 18’’