• 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 2   The  Catalan  garden
Ch 2a

 21  January 2016
slides Ch2a    (pdf  29 Mo)          
video Ch2a  link to YouTube  (1h 21mn)
video Ch2a  link to bilibili
The Catalan garden  2  video:  22’‘    video
Binary trees and complete binary trees  7   2’  33’’  video
        binary trees: definition  11   3’ 08’’  video
        left - right subtrees, subtrees, left - right child  13   4’ 36’’  video
        double, right simple, left simple vertex, leaf  14   5’ 16’‘   video
        path in a tree, left-height, right-height, height  15   6’ 07’’  video
        left, right principal branch  16  7’ 46’’  video
        preorder  17  8’ 24’‘   video
        inorder  21   12’ 13’‘  video
        postorder  23  13’ 05’’  video
bijection binary trees - complete binary trees  26  15’ 10’’  video
exercise, bijective proof of the multiplicative recurrence  
        for Catalan numbers  30  16’ 16’’  video
planar trees  31  17’ 21’’  video
        preorder  35  20’ 16’’  video
        bijection binary trees - (forest of) planar trees  36  21’ 37’’ video
paths: Dyck paths, 2-colored Motzkin paths, Lukasiewicz paths  45  27’ 03’’  video
        Motzkin paths  48   28’ 45’’  video
        2-colored Motzkin paths  50  30’ 41’’  video
        Lukasiewicz paths and langage  51-52  33’ 01’’  video
bijections paths to paths  54  37’ 46’’  video
        bijection  2-colored Motzkin paths - Dyck paths  55  38’ 04’’  video
        exercise: prove bijectively Touchard’s identity  59   43’ 50’‘   video
        bijection Dyck paths - Lukasiewicz paths 60  45’ 16’‘   video
bijections  trees to paths  64   49’ 24’’  video
        bijection complete binary trees - Dyck paths  65  50’ 14’‘  video
        the bijection with violins  70  52’ 55’’  video
        the reverse bijection 72  54’ 57’’  video
        bijection binary tree - 2-colored Motzkin path  90  56’  38’’  video
        bijection planar trees - Dyck paths  92  58’ 21’’  video
        bijection plane trees - Lukasiewicz paths  98  1h 2’ 08’’  video
staircase polygons 103  1h 4’ 40’’  video
        bijection staircase polygons - 2-colored Motzkin paths  105  1h 6’ 25’’  video
        bijection staircase polygons - Dyck paths  110  1h 10’ 27’’  video
non-crossing partitions  117  1h 14’ 15’’  video
        bijection non-crossing partitions - Dyck paths  119  1h 15’ 32’’  video
the end 125  1h 20’ 50’’

Ch 2b

         28  January 2016
slides_Ch2b     (pdf   22 Mo)              
video Ch2b  link to YouTube     (1h 35mn)
video Ch2b  link to bilibili                         
The Catalan garden 2  10’  video
non-crossing partitions 6  1’  41’‘   video
        bijection non-crossing partitions - Dyck paths 8  3’  06’‘   video
triangulation of a convex polygon  13 5’  50’’  video
A letter from Leonhard Euler to Christian Goldbach 15  7’  33’’  video
        Euler polyhedra formula and triangulations  21  9’  25’’  video
        bijection triangulations- complete binary trees 23  12’  18’’  video
        reciprocal bijection  31  15’  28’’  video
some other interpretations of Catalan numbers: chord diagrams  33  17’  21’‘   video
        bijection chord diagrams -- Dyck paths  36  18’  25’‘    video
Catalan permutations 40  19’  48’’  video
        permutations sortable by one stack  41  20’  01’’  video
        bijection with Dyck paths  51  21’  20’’  video
        relation Catalan permutations -- non-crossing partitions  52  21’  50'’  video
        forbidden pattern  54  23’  37’’  video
        (312)-avoidig permutations 55  26’  02’’  video
pairs of sequences  57  28’  43’‘  video
bijective proof of the multiplicative recurrence for Catalan numbers 60  32’  51’’  video
bijective proof  of Touchard's identity 73  38’  48’’  video
logarithmic height of a Dyck path  103  44’  01’’  video
        Strahler number of a binary tree  107  46‘  42‘   video
        functional equation for logarithmic height and for Strahler number  108 47‘  34’‘    video
        generating function for Strahler numbers  118  56’  08’‘   video 
the end 119  56’  20’’  video

complement to Ch 2b:  56’  20’’  video_Strahler
Strahler number of trees in various sciencesslides_Strahler  (pdf   11 Mo)

average of Strahler number  2  56’  32’’  video
minimum number of registers to compute an arithmetic expression  4  59’  06’’  video
        pebbles problem  7  1h  00’  14’’  video
bifurcation ratio in hydrogeology 24  1h  02’  28’’  video
ramification matrix 26  1h  07’  05’‘   video
DLA and viscuous fingering 28  1h 09’  56’’  video
galactograms  30  1h  11‘  34’‘    video
synthetic images of trees  33  1h  12’  40’‘   video
        random binary search tree 40-41  1h  15’  00’’  video
        random binary tree 42  1h  15’  23’’  video
        mixing ramification matrices 44  1h 16’  01’‘   video
        landscape  49  1h  17’  18’’  video
the end 50  1h  17’  29’‘   video

complement to Ch 2b:  1h  18’  00’‘video_Temperley-Lieb
Catalan numbers and Temperley-Lieb algebra TL_n slides_TLn  (pdf   5 Mo)

an element of TL_n  2  1h  18’  19’‘   video
product in TL_n    3  1h  19’  22’‘   video
generators and relations for TL_n    5  1h  19’  59’‘   video
heaps of dimers and elements of TL_n   8  1h  23‘  19’‘    video
condition for a heap of dimers to give an element of a basis of TL_n   13  1h  23’  57’’  video
staircase decomposition of a heap of dimers  15  1h  25’  29’’  video
an element of a basis for TL_n   18  1h  27’  44’’  video
        in bijection with a Dyck path   22  1h  31’  30’’  video
        in bijection with a staircase polygon  26  1h  31’  53’’  video
heap of dimers and permutations 29-30  1h  32’  20’’  video
an element of a basis for TL_n  in bijection with a (321)-avoiding permutation 33  1h  33’  00’’  video
from a staircase polygon to a (321)-avoiding permutation 34
the end  35  1h  34’  48’’

Ch 2c

           2  February 2016
slides_Ch 2c   (pdf  17 Mo)          
video Ch2c  link to YouTube      (1h 21mn)
video Ch2c  link to bilibili
the cyclic lemma  3  0’  07’’  video
        conjugate and primitive words  4  0’  17’’  video
        the cyclic lemma  5  3’  59’’  video
        corollary: bijective proof for the formula giving the Catalan number  11  14’  59’’  video
        corollary: formula for  -p  12  19’  00’  00’’  video
        corollary: formula for the alpha distribution (ballot numbers)  13  20‘  28’‘    video
the ballot problem 15 22' 50'' video
        a Catalan triangle  16  24’  26’’  video
        Arbogast tableau  17  27’  22’‘   video
bijective proofs for Catalan numbers  20  30’  14’’  video
exercise: bijective proof of (n+1)C_n = binomial (2n,n), solution with binary trees and bilateral Dyck paths  22   31' 10''  video
exercise: find a bijective proof of (n+1)C_n = binomial (2n,n) with only Dyck paths and bilateral Dyck paths  26   33' 35"  video
Lagrange inversion formula and the cyclic lemma  27  34’  21’’  video
            some  problems on the video between 42’ 20’’  and  43’ 22’’
the reflection principle  40  54’  32’’ video
        the general formula  44  1h  01’  29’’  video
        formula for the double alpha distribution 46  1h  02’  25’’  video
        formula for the alpha distribution  47  1h  03’ 18’‘   video
the reflection principle  (again)  48  1h  04’  03’‘   video
        formula for the beta distribution (Narayana numbers)  51  1h  05’  30’‘   video
three distributions in the Catalan garden  54  1h  09’  55’’  video
        the  alpha  distribution  55  1h  10’  06’’  video
        the beta distribution  58  1h  12’  43’‘   video
        the gamma distribution  62  1h  16’  18’‘   video
solution of exercise: semi-pyramids of dimers  65  1h  16’  30’‘   video
        from Dyck paths to semi-pyramids of dimers  (video with violin)  70  1h  19’  55’’  video
the end  73  1h  21’  15’’

Ch 2d

         4 February  2016
slides_Ch2d     (pdf 18 Mo)        
video Ch2d  link to YouTube      (1h 27mn)
video Ch2d  link to bilibili
from previous lecture: the cyclic lemma  3  00’  52’’  video
planar maps and the cyclic lemma  10  5’  11’‘   video
        planar maps: definition  11  5‘  30’‘    video
        rooted planar maps: definition  12  6’  03’‘   video
        Tutte formula for the number of rooted planar maps  13  6‘  21’‘    video
        blossoming trees  16  9‘  14’‘   video
        bijection planar maps -- quartic planar maps  18  10‘  35’‘   video
        reverse bijection  22  15’  02’’ video
Schaeffer’s bijection between well balanced blossoming trees and quartic rooted maps  25  17‘  13’’  video
        blossoming trees  27  17’  39’‘   video
        border word  28  17’  57’‘   video
        partial closure of a blossoming tree  37  21’  24’‘   video
        well-balanced blossoming tree: definition  42  25’  24’‘   video
        complete closure of a well-balanced tree  44  29’  07’‘   video
introduction to q-analogues with  q-Catalan  53  33’  52’‘    video
        q-binomial coefficients  56  37‘  29’‘     video 
        the maj q-Catalan  57  40‘  05’‘    video
        the area q-Catalan  60  43’  54’‘   video
        Polya q-Catalan  63  47’  00’’  video
complement:  (q,t)-Catalan  64  49’  04’’  video
        the bounce parameter  65  49’  34’‘   video
        the (q,t)-Catalan polynomial  68  53‘  28’‘   video
        complement to the complement: original definition by Garsia-Haiman  70  56’  21’’  video
some exercises using Catalan factorization and Catalan words  75  58’  18’’ video
        Catalan factorization of a word  76  58’  36’’  video
        Catalan word and the bijection theta  78  1h  00’ 41’’  video
        the bijection rho  80  1h  03’  46’‘   video
        exercise: average height of the final point of left factors of Dyck paths  83  1h  06’  33’’  video
        exercise: average area of Dyck paths  84  1h  07’  44’’  video
        exercise: average path length of a binary tree  86  1h  09’  18’’  video
        exercise:  average length of the left branch of a random binary tree  88  1h  10’  54’’  video
complement:  the TASEP  89  1h  11’  20’’  video
        Markov chain and stationary probabilities  93  1h  14’  51’’  video
        path interpretation of the stationary probabilities of the TASEP  96  1h  15’  59’’  video
        canopy of a binary tree  97-98  1h  17’  34’’  video
        interpretation of the stationary probabilities with binary trees  99  1h  19‘  03’‘    video 
        exercise: formula for the partition function of the TASEP  103  1h  21‘  20’‘    video
        bijection pair of paths -- binary trees preserving the canopy  100  1h  22’  21’’  video
the end  104  1h  26’  31’’