• 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 III
The cellular ansatz:  bijective combinatorics and quadratic algebra

The Institute of Mathematical Sciences, Chennai, India  (January-March 2018)

Chapter 4   Trees and Tableaux
Ch 4a  Trees and Tableaux: binary trees and Catalan alternative tableaux

March 1, 2018
slides of Ch 4a   (pdf,  28 Mo)                 
video Ch4a: link to Ekalavya  (IMSc Media Center)
video Ch4a: link to YouTube
video Ch4a: link to bilibili
TASEP and Catalan alternative tableaux   3   0:38
Catalan alternative tableaux   9   2:37
definition   10   2:42
Characterisation of Catalan alternative tableaux
Catalan permutation tableaux: definition   14   5:28
(another) example   16   7:48
construction of the blue cells (from the red cells)   20-22   8:05
Binary trees and complete binary trees   28   9:54
definition of a binary tree   29   10:44
classical enumerative combinatorics: recurrence relation for Catalan numbers   32   13:10
modern enumerative combinatorics: operations on combinatorial objects and algebraic equation   33-34   13:49
exercise: "complete" bijective proof for the Catalan numbers   38   15:34
bijection binary trees -- complete binary trees   42   17:48
height, left height, right height in a binary tree   47   19:20
left and right principal branch in a binary tree   48   19:57
preorder traversal of a binary tree   49   20:54
inorder (symmetric order) traversal of a binary tree   52   21:51
Bijection binary tree -- pair of paths (u,v)   55   23:56
Reverse bijection pair of paths (u,v) -- binary tree   61   34:12
the "push-gliding" algorithm   62-71   34:21   
Bijection Catalan alternative tableaux -- binary trees   72   41:58
Second bijection  Catalan alternative tableaux -- binary trees   78   46:21
reverse bijection   96   50:45
TASEP, Catalan alternative tableaux and binary trees   108   53:15
expression of the 2 parameters TASEP stationary probability with binary trees and canopy   111   55:01
bijective proof for the partition function   112-114   56:44
Bijection Catalan alternative tableaux -- pairs of paths (u,v)   116  1:04:45
reverse bijection   120   1:07:56
commutative diagram: Catalan alternative tableaux - binary trees - pair of paths (u,v)   128-129   1:10:19   
The Adela bijection: demultiplication (of equations) in the PASEP algebra   130   1:15:15
Adela bijection (for alternative tableaux)   134   1:17:38
the Catalan case: Adela duality   135-136   1:21:04
TASEP, Catalan tableaux and pair of paths (u,v)   137   1:22:52
relation with the Shapiro-Zeilberger interpretation   139   1:23:31
2-parameters stationary probabilites as a determinant (Olya Mandelshtam)   141   1:25:05
LGV proof with dual configuration of paths for Narayan-Kreweras determinant   144   1:27:11
The end   145    1:28:14

Ch 4b   Trees and tableaux: the Loday-Ronco algebra of binary trees

April 16, 2018
slides of Ch 4b   (pdf,  23 Mo)                 
video Ch4b: link to Ekalavya  (IMSc Media Center)
video Ch4b: link to YouTube
video Ch4b: link to bilibili
graded Hopf algebra  4     0:44
reminding: increasing binary trees, canopy and up-down sequence    5     2:15
two Hopf algebras: Malvenuto-Reutenauer (permutations) and Loday-Ronco (binary trees)   18     14:56
definition of the map psi*    20     15:57
definitions: standartisation of a word and Malvenuto-Reutenauer product   21     17:32
definition of the Loday-Ronco product   22     25:08
Loday-Ronco product with an example   23     27:22
"Jeu de taquin" for increasing woods and increasing binary trees   24     32:36
increasing woods: definition   25     33:02
slidings in an increasing woods  27     36:32
jeu de taquin for an increasing woods     28     39:26
invriance of the symmetric order for an increasing wood   29     40:39
example: from a permutation to its "déployée"   30-42     43:05
Catalan alternative tableaux  (reminding of Ch4a)  45   47:03
definitions: alternative tableaux and Catalan alternative tableaux (reminding Ch4a)   46-47     47:10
characterisation of Catalan alternative tableaux with Catalan permutation tableaux   48     49:42
definitions: permutation tableaux and Catalan permutation tableaux   49     50:51
Catalan alternative tableaux of rectangular shape   54     52:44
BIjection Catalan alternative tableaux -- binary trees (reminding Ch4a, 78-107)   57     54:17
(with jeu de taquin on unlabelled woods)   58-70    
profile and canopy in this bijection   71     38:15
free columns, free rows and principal branches of the corresponding binary tree   72-73     59:19
Catalan alternative tableaux underlying the  "Jeu de taquin" for increasing woods   74     1:01:03
Construction of the Loday-Ronco product from the Malvenuto-product of permutations   95     1:04:06
Expression of the Loday-Ronco product with rectangular Catalan alternative tableaux   104     1:08:23
Analog of the Loday-Ronco product for Catalan alternative tableaux   114     1:12:52
The  "sharp" product   126     1:17:49
definition: sharp product of two binary trees   131   1:19:00
Loday-Ronco product and the sharp product   133     1:20:46
the sharp product of two Catalan alternative tableaux     135     1:21:48
the Loday-Ronco product in term of Catalan tableaux     141     1:24:03
the end 145   1:27:28

Ch 4c   Trees and tableaux: alternative binary trees, non-ambiguous trees and beyond

April 19, 2018
slides of Ch 4c   (pdf,  32 Mo)                 
video Ch4c: link to Ekalavya  (IMSc Media Center)
video Ch4c: link to YouTube
video Ch4c: link to bilibili
 From Ch4b:" jeu de taquin" for an increasing wood and Catalan alternative tableau   3     0:44
Alternative binary trees   9     02:30
definition: edge-alternative binary tree   10     02:52
definition: edge alternative wood  11   03:58
definition: alternative binary tree   12     05:31
bijection alternative binary tree and permutation   14     06:46
"Jeu de taquin" for alternative binary trees and woods   17     11:42
definition of the 3 possible slidings   19     12:34
the bijection alternative tableaux -- alternative trees (with jeu de taquin)  20-37     14:39
Reminding the "exchange-fusion" algorithm   38     19:35
Reminding the bijection alternative tableaux -- permutations  (inverse exchange-fusion)   45     20:50
Comparison of the "jeu de taquin" bijection with the "exchange-fusion" bijection   61    24:30
the twisted symmetric order   63     24:50
Genocchi sequence of a permutation (reminding)     67     30:30
Comparison of the underlying binary trees (alternative tableaux and alternative binary trees)   69     32:38
Second version of the bijection alternative tableaux -- alternative binary trees   74     33:46
Tree-like tableaux   79     36:02
definition: tree-like tableaux   (reminding)   83     36:45
Catalan tree-like tableaux: two bijections with binary trees (reminding)   86     39:30
Non-ambiguous trees   91     40:32
intervals of permutations having the same underlying non-ambiguous tree  98-104     42:33
hook formula for non-ambiguous trees   106     44:38
formula for the number of non-ambiguous trees (with Stirling numbers)   108     50:08
Complete non-ambiguous trees, Bessel functions and heaps of "sticks"  109     50:54
Emma Jin's bijection between complete non-ambiguous trees and some heaps of "sticks"   111-116     54:09
q-Polya numbers for parallelogram polyominoes, q-Bessel and heaps of segments   119-120     1:03:19
Bijection parallelogram polyominoes -- binary trees via non-ambiguous trees   121     1:05:00
Tree-like tableaux are Q-tableaux or the reverse PASEP quadratic algebra   127     1:07:12
In conclusion: the philosophy of the cellular ansatz   141     1:10:38
reminding the trilogy for RSK: growth diagrams and representation of the quadratic algebra UD=DU+Id,
edge local rules and demultiplication of equations   142-151     1:10:50
reminding commutations diagrams from a representaion of the PASEP algebra   153     1:14:48
duplication of equations in the PASEP algebra: the Adela bijection   158-160     1:16:02
duplicaion of equations in the reverse PASEP algebra (with 4 generators)   165-168     1:18:38
equivalence with the commutations diagrams   169-173     1:18:59
A new bijection: duplication of equations in the reverse PASEP quadratic algebra   174     1:19:40
The proposed duplication of equations with only two operators   176     1:20:18
The "Tamil bijection" between alternative tableaux and some words   178     1:21:24
interpretation of the Tamil bijection with the underlying binary tree   181     1:23:38
the case of Catalan tableaux   185   1:24:58
example with parallelogram polyominoes  186     1:25:38
example: coding of a binary tree with the Tamil bijection  192     1:26:59
Many thanks   193     1:29:12
The godess Saraswathi   194     1:30:27