CoursE  X.V.  IMSc  2016

 
 

Course  IMSc  Chennai, India 

January-March 2016

An introduction to enumerative, algebraic and

bijective combinatorics



Ch 2   The  Catalan  garden

      21  January 2016

                                slides Ch 2a    (pdf  29 Mo)           video Ch 2a    (1h 21mn)


Ch 2a

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  Ch 2b           (1h 35mn)                          

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’  51’’  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 number of trees in various sciences                             slides  (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

Catalan numbers and Temperley-Lieb algebra TL_n                 slides  (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 Ch 2c      (1h 21mn)


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‘  27’‘    video

        a Catalan triangle  16  24’  26’’  video

        Arbogast tableau  17  27’  22’‘   video

bijective proofs for Catalan numbers  20  30’  14’’  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 Ch 2d         (1h 27mn)


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’’



last update: 16  April 2016


return to:

courses  website

main Xavier Viennot  website