XAVIER VIENNOT
  • PART I
    • 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
    • list of bijections
    • index
  • PART II
    • 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
    • Some lectures related to the course
  • PART III
    • 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
    • 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)

List of 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