CoursE  X.V.  IMSc  2016

 
 


Course  IMSc  Chennai, India 

January-March 2016

An introduction to enumerative, algebraic and

bijective combinatorics



Ch 1  Ordinary  generating  functions        

    7 January 2016

                                slides Ch1a     (pdf    26  Mo)        video Ch1a    (1h 22mn)


Ch 1a

an example: binary trees    slide: 3    25 ‘‘   video

        Euler triangulations  13      6’ 24’’  video

intuitive introduction to ordinary generating functions and formal power series  17  9’ 45’’  video

        a little exercise: Fibonacci generating function  23  11’ 11 ‘‘    video

formal power series algebra: formalisation 29   13’ 24’‘   video

        algebra of formal power series  33   15’ 25’’  video

        summable family  35   18’ 13’‘   video

        infinite product  38  20’ 45’‘   video

        other  operations 40  22’ 12’‘   video

        free monoid and non-commutative power series  44   28’ 5’‘   video

operations on combinatorial objects, intuitive introduction with binary trees  47  32’ 10’‘   video

operations on combinatorial objects, formalisation 55   37’ 31’‘   video

        sum 59   47’ 12’‘    video

        product  60    48’ 23’‘    video

        sequences  61   50’ 00’‘   video

operations on combinatorial objects, example: integer partitions, q-series  63   51’ 28’‘   video

        generating function for (integer) partitions  73   58’ 39’’  video

        execrcise:  D-partitions  74   59’ 50’‘     video

Rogers-Ramanujan identities  76  1h 2’ 54’‘     video

bijective proof of an identities  82   1h 8’ 21’‘     video

visual proof:Pythagore  84    1h 9’ 1’‘    video

bijective proof of an identity, the bijective paradigm 112   1h  10’ 12’‘   video

bijective combinatorics, example: Catalan numbers  126   1h  14’ 15’‘    video

Dyck paths  133     1h 19’ 07’‘   video

the end 139   1h 22’ 40’’


   12 January 2016

                                slides Ch1b     (pdf    20  Mo)        video Ch 1b  (1h 22mn)


Ch 1b

from the previous lecture   slide:3     video: 5’‘   video

operation on combinatorial objects, derivative 16   4’ 45’‘    video

operation on combinatorial objects, derivative, example: heaps of dimers 20   10’ 58’‘    video

        heaps of dimers: definition  21  11’ 22’‘    video

        the logarithmic lemma for heaps of dimers  18’ 40’‘    video

        pyramid and maximal piece: definition  18’ 40’‘     video

proof of the logarithmic lemma for heaps of dimers  28   22’ 30’‘    video

exercises:  pyramids and algebraic generating functions  37  29’ 56’‘    video

        semi-pyramids of dimers  38    30’ 07’‘   video

        pyramids of dimers  41   32’ 17’‘    video

        bilateral Dyck paths  42   34’ 07’‘    video

operation on combinatorial objects, substitution, example:  Strahler number of a binary tree  44   37’ 49’‘   video

        substitution  45   38’ 26’‘   video

        Strahler number of a binary tree: definition  47   42’ 00’‘   video

        Hydrogeology  49-51   44’ 37’’  video

        functional equation for two variables generating function of Strahler number  52  47’ 19’‘   video

        experimental combinatorics  53-59  50’ 2’‘   video

        Pascal, Pingala and Fibonacci  60   55’ 34’‘     video

        substitution in binary trees  65-72   58’ 21’‘       video

generating functions: rational, algebraic, D-finite  76   1h  5’ 5’‘    video

rational generating functions  79   1h  9’ 13’‘    video

        weighted paths  81     1h  9’ 45’‘    video

        self-avoiding path and circuit 83   1h 11’ 48’‘    video  

        elementary circuit and cycles  84  1h 12’ 24’‘     video

        main proposition: generating function for weighted paths in a graph as  N_(i,j)/D  86  1h 13’ 47’‘   video

        linear algebra proof of the main proposition  87-91   1h 18’ 25’‘    video

the end 92  1h 22’ 31’’



   14  January  2016

                                slides Ch1c     (pdf   20  Mo)         video Ch 1c   (1h 24mn)


Ch 1c

from the previous lecture    slide: 3    15’‘    video

bijective proof of the identity  N_(i,j)/D  9   3’ 09’‘    video

        construction of the involution  phi  12  9’ 49’‘      video

an example and an exercise for N_(i,j/)D  19  25’ 30’‘   video

        an example: paths on a graph with 2 vertices  20  25’ 36’‘   video

        exercise: directed path  21  28’ 24’‘   video

another example for N_(i,j)/D: bounded Dyck paths  23  32’ 03’‘    video

        Fibonacci polynomials and matchings  30   36’ 31’‘     video

Fibonacci polynomials  34  39’ 55’‘   video

        generating functions for Fibonacci polynomials  37 40’ 30’‘   video

        exercise: coefficient of the Fibonacci polynomials 39   45’ 38’‘    video

        Pingala and Fibonacci  40-41   46’ 18’‘     video

exercise: Fibonacci numbers and polyominoes  42   49’ 02’‘    video

Fibonacci and Tchebychef polynomials  44   53’ 08’‘    video

Lucas and Tchebychef polynomials  50   59’ 25’‘   video

        exercise: relation Fibonacci and Lucas polynomials  55   1h 3’ 10’‘   video

complement: matching polynomial of a graph  56   1h 3’ 45’‘   video

        zeros of the matching polynomial of a graph 60  1h 5’ 53’‘     video

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

        logarithmic height of a Dyck path  68  1h 9’ 58’‘    video

        generating function for Strahler  numbers  74   1h 16’ 08’‘   video

exercise, proof by killing involution: Euler’s pentagonal theorem  76  1h 17’ 55’‘    video

the end  81  1h 24’18’’



    19  January 2016

                                slides Ch1d    (pdf  24 Mo)           video Ch 1d   (1h 22mn)      


Ch 1d

from the previous lecture, proof of the Euler’s pentagonal theorem      slide 3  video: 15’‘   video

another exercise with a sign-reversing involution   10’ 35’‘   video

        (generating function for heaps of dimers on a segment)  14  10’ 35’‘   video

more about rational series  16  12’ 57’‘    video

        zeros of Fibonacci polynomials  19    17’ 30’‘    video

        zeros of Lucas polynomials  20   18’ 40’‘    video  

Lagrange inversion formula  21  19’ 01’‘    video

algebraicity with hidden decomposable structures, example: planar maps  25  26’ 36’‘    video

        system of equations for rooted planar maps and the bijection Cori-Vauquelin 31  32’ 03’‘   video

        direct formula for the number of rooted planar maps  33  34’ 18’‘    video

        blossoming trees and idea of Schaeffer bijection  37  36’ 21’’  video

complements:  algebraicity with hidden decomposable structures, example: directed animals  41  38’ 35’’  video

        system of equations for directed animals  44  40’ 57’’  video

        exercise: system of equations for prefix of Motzkin paths 45    41’ 25’‘    video

        random directed animals  47-48  45’ 49’‘   video

an anecdote  (about directed animals)  49  46’ 18’‘    video

complements: algebraicity with hidden decomposable structures, example: convex polyominoes  54  49’ 31’’  video

        exercise: directed and vertically convex polyominoes  59  50’ 22’‘   video

        formula for the number of convex polyominoes with given perimeter  64  52’ 50’‘   video

        random convex polyominoes  (with fixed perimeter)  66  53’ 31’‘   video

        random convex polyominoes (with fixed area)  67-68  54’ 17’‘    video

rational and algebraic generating functions, a flavor of theoretical computer science,

        Schützenberger’s methodology coding with words of algebraic languages  69  54’ 51’‘   video

        algebraic language and algebraic grammar  70  55’ 22’’  video

        non-ambiguous grammar for the Dyck language, derivation tree  73  1h 3’ 05’‘   video

        Chomsky-Schützenberger theorem  75  1h 5’ 29’‘   video

        algebraic equation for prefix of Motzkin paths  76 1h 9’ 54’‘    video

        automaton and rational language  77  1h 10’ 09’‘   video

generating functions, algebraic, D-finite or not D-finite ?  81  1h 15’ 26’‘   video

        paths in a quadrant  83  1h 16’ 16’’  video

        Kreweras and Gessel paths  84  1h 17’ 29’‘   video

        catalytic variables and kernel methodology 85  1h 18’ 12’‘   video

        the queen  1h 20’ 45’‘   video

        an example of generating function not D-finite: connected heaps of dimers 87 1h 21’ 25’‘    video

the end  88  1h 22’ 18’’





last update: 1 6 April 2016


return to:

courses  website

main Xavier Viennot  website