CoursE  X.V.  IMSc  2016

 
 

Course  IMSc  Chennai, India 

January-March 2016

An introduction to enumerative, algebraic and

bijective combinatorics


Bijections



Trees

bijection binary trees — complete binary trees, Ch2a  26    video

bijection binary trees — (forests of) planar trees, Ch2a  36    video

bijection binary trees — 2-colored Motzkin paths, Ch2a  90   video

bijection (complete) binary trees — Dyck paths, Ch2a  65  video  and (with violin) 70  video

bijection (complete) binary trees — triangulations  Ch2b 31  video

bijection planar trees — Dyck paths, Ch2a  92   video 

bijection planar trees — Lukasiewicz paths, Ch2a  98  video


Paths

bijection Dyck paths — (complete) binary trees , Ch2a  65  video  and  72   video

bijection Dyck paths — planar trees, Ch2a  92  video

bijection Dyck paths — 2-colored Motzkin paths, Ch2a  55  video

bijection 2-colored Motzkin paths — binary trees Ch2a  90   video

bijection Dyck paths — semi-pyramids of dimers, Ch2c  71 (with violin) video

bijection Lukasiewicz paths — Dyck paths , Ch2a  60  video

bijection Lukasiewicz paths — planar trees, Ch2a  98  video


Staircase polygons

bijection staircase polygons — 2-colored Motzkin paths, Ch2a  105  video

bijection staircase polygons — Dyck paths, Ch2a  110    video

bijection staircase polygons — basis of TL_n , Ch2b-complements-TLn, 23  video

bijection staircase polygons — (321)- avoiding permutations, Ch2b-complements-TLn,  34 (no video)


Non-crossing partitions

bijection non-crossing partitions — Dyck paths, Ch2b  8  video

bijection non-crossing partitions  — Catalan permutations , Ch2b  53  video


Planar maps

bijection planar maps — planar quartic maps, Ch2d  18  video

bijection rooted planar maps — rooted planar quartic maps, Ch2d  20  video

                reverse bijection, Ch2d  22  video   more explanations in this  video

bijection rooted planar quartic maps — well balanced blossoming trees,

                (Schaeffer bijection) Ch2d  25-44   video

bijection triangulations — (complete) binary trees, Ch2b  23 (with violin)  video


Temperley-Lieb algebra  TL_n

bijection basis of TL_n — some heaps of dimers, Ch2b-complements-TL_n, 18  video

bijection basis of TL_n — Dyck paths,  Ch2b-complements-TL_n, 19  video

bijection basis of TL_n — staircase polygons,  Ch2b-complements-TL_n, 23  video

bijection basis of TL_n — (321)- avoiding permutations, Ch2b-complements-TL_n, 31  video


Permutations

bijection permutations (cycles notation) — permutations (word), Ch4a  7-8  video and 20 video

bijection permutations — assemblées of increasing arborescences, Ch4a  96  video

bijection permutations — increasing binary trees, Ch4a  75-76   video

bijection permutations — inversion table,  Ch4a  29-30  video 

                reverse  bijection  33-44  video

bijection permutations — inversion table (with the Maj index), Ch4a  52-72  video

bijection permutations — pair of Young tableaux same shape (Robinson-Schensted, RS)

                RS with Schensted insertions, Ch4c  24-46  video

                RS with light and shadows, Ch4c  53-73   video

                RS with growth diagrams  Ch4d  4-26   video 

                RSK matrices — pairs of semi-standard Young tableaux, Ch4d  63  video

bijection involutions (no fixed points) — oscillating tableaux, Ch4d  52-55  video

bijection involutions (no fixed points) — Hermite histories, Ch4b 68-77  video

bijection Catalan permutations — non-crossing partitions, Ch2b  53  video

bijection (321)- avoiding permutations — basis of the TL_n,  Ch2b-complements-TLn, 31  video


Histories

bijection Hermite histories — chord diagrams, Ch4b  68-77   video

bijection Laguerre histories — permutations (with binary trees), Ch4b  11-22  video

                (with words), Ch4b  23-33   video

                reciprocal bijection Ch4b  34-40   video


Rook placements

bijection rook placements — oscillating tableaux, Ch4d 52  video

bijection rook placements — Hermite histories, Ch4d 53  video

bijection rook placements — involutions with 2-colored fixed points, Ch4d 56  video

bijection staircase rook placements — Partitions, Ch4d  58  video


Non-intersecting configurations of paths

bijection plane partitions — non-intersecting configurations of paths, Ch5a  97-105  video

bijection aztec tilings — non-intersecting configurations of Schröder paths, Ch5b  94  video

bijection semi-standard Young tableaux — non-intersecting configurations of paths,

             Ch5a  69-70  (by rows)   video

             Ch5b  19-22  (by rows)  video  (by columns)   video


Bijective proof of identities

visual proof of Pythagorus theorem,  Ch1a  84   video

bijective proof  of an identity with q-series,  Ch1a  113   video

bijective proof for the number of aztec tilings, Ch5b  94-113  video

bijective proof for the number of Baxter permutations,

            Ch4b  108-122,    video    (bijection  Baxter permutations triple of paths with Laguerre histories)

            and   Ch5a  45-48    video     (triple of paths as binomial determinant) 

            and  Ch5a   81-86  video    (with the formula  contents / hook length)

bijective proofs for the formula giving the Catalan number:

            the philosophy of bijective proofs for various  Catalan formulae, Ch1a  127  video              

            bijective proof of the multiplicative recursion for Catalan numbers,    Ch2b  60   video

            bijective proof  related to the cyclic lemma,  Ch2c 11  video

            bijective proof with binary trees, Ch2c  22  video ,   with  Dyck paths,  Ch2d  80    video

            bijective proof with the reflexion principle, 44  video 

bijective proof of Lagrange inversion formula, Ch2c  28-39   video

bijective proof of Mehler identity, Ch3b  27-34    video

bijective proof of Touchard identity, Ch2b  73   video





last update: 16 April 2016


return to:

courses  website

main Xavier Viennot  website