• 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 5    Tableaux and orthogonal polynomials
Ch 5a     Moments of orthogonal polynomials with weighted Motzkin paths, continued fractions and the Flajolet Lemma, 
Laguerre, Hermite and Charlier histories

March 5, 2018
slides of Ch 5a   (pdf,  33 Mo)                 
video Ch5a: link to Ekalavya  (IMSc Media Center)
video Ch5a: link to YouTube
video Ch5a: link to bilibili
some trigonometry ...   3   1:06
Tchebychef polynomials (2nd kind)   4   1:11
Fibonacci polynomials   5   2:14
combinatorial proof of orthogonality   7-8    4:34
Combinatorial interpretations of some orthogonal polynomials   9   6:11
Hermite polynomials   10  7:34
Laguerre polynomials   12   11:52
Formal orthogonal polynomials: definition, moments   15   16:08
Orthogonal polynomials, the PASEP model in physics and ASM   19   24:01
Askey tableau of (classical) orthogonal polynomials   23   26:41
Combinatorial theory of orthogonal polynomials, the two approaches: coefficients or moments   25   28:19   
example of combinatorial proof: Mehler idendity for Hermite polynlomials   27   30:28
(formal) Favard theorem   29   34:48
Moments and weighted Motzkin paths   33   39:30
associated tridiagonal matrix   38   43:53
Equivalence with analytic continued fractions   39   45:14
Jacobi contined fraction   40   45:22
Stieljes continued fraction   41   46:11
The fundamental Flajolet Lemma  44    49:27
the "Lemma"   47   49:58   
Proof of the   Lemma   48   50:14
Back to the relation between orthogonal polynomials and (analytic) continued fractions   60   52:55
Laguerre histories and moments of Laguerre polynomials   66   58:35
Reminding the bijection permutations -- Laguerre histories   73   1:03:45 
Weighted Laguerre histories   78   1:09:22
interpretation of the moments of Laguerre polynomials with the parameters alpha   83   1:11:57
restricted Laguerre histories   85   1:14:39
Sheffer orthogonal polynomials   87   1:16:12
Charlier histories   90   1:18:47
3 terms recurrence relation and moments of Charlier polynolmials   91   1:18:56
bijection set partitions and Charlier histories   92-100   1:19:41
Hermite histories   101   1:24:27
Euler continued fraction   103   1:25:05
bijection chord diagram (involution with no fixed point) and Hermite histories   107-111   1:27:50
oscillating tableaux, rook placements and Hermite histories   112-113 (see Ch1e, p.90-117)   1:29:19
Scheffer orthogonal polynomials: Hermite, Laguerre, Charlier, Meixner I and II   114   1:29:47
the five moments under the same roof with Laguerre histories   117   1:30:11
The end   118

Ch 5b   permutation and inversion table, q-Laguerre I and II, q-Hermite I,
the bijection permutations subdivided Laguerre histories, Dyck tableaux, Laguerre heaps

March 8, 2018
slides of Ch 5b   (pdf,  30 Mo)                 
video Ch5b: link to Ekalavya  (IMSc Media Center)
video Ch5b: link to YouTube
video Ch5b: link to bilibili
Reminding of Ch 5a: orthogonal polynomials, continued fraction, Laguerre and Hermite polynomials   3   0:27
Inversion table, q-analogue   14   7:11
sub-exceedant functions: definition   15   7:25
notations: q-analogue of n and of n!   16   8:20
the bijection permutation -- inversion table  17-18   11:11
the reverse bijection: from a sub-exceedant function to a permutation   19-30   12:58
q-Laguerre II polynomials  (the moments are the q-analogue of n!   32   15:33
q-Laguerre I polynomials  (the q-Laguerre related to the PASEP   33   20:11
q-Hermite I polynomials   34   21:35
Reminding Ch5a, Hermite histories  35   22:18
Subdivided Laguerre histories   42   27:47
a continued fraction of Euler: generating function of n! as a Stieljes continued fraction   46   30:25
subdivided Laguerre history: definition   48   32:13
Bijection permutations -- subdivided Laguerre histories   49   34:05
bijection permutation on n -- some pairs of involutions on 2n   50   34:10
subdivided Laguerre history as a pair of two Hermite histories   54   39:40
Dyck tableaux as subdivided Laguerre histories   57   43:31
Dyck tableau: definition   58   43:47
Direct bijection permutations -- Dyck tableaux   63   48:52
description of the bijection permutation -- Dyck tableaux   66-74   49:15
Reverse bijection: from Dyck tableaux to Laguerre heaps (=multilinear heaps of pointed segments)   76   52:34
from a Dyck tableau to a "sequence of lines and points"   78   52:40
from a "sequence of lines and points" to a Laguerre heap (=multilinear heap of pointed segments)  79-93   54:40
reminding from BJC II, heaps of segments   98   1:00:51
multilinear heaps of pointed segments, definition: 
(after the video, I propose to call them Laguerre heaps)   99   1:01:11
Lexicographic normal form of a heap (reminding BJC II)   100     1:06:04
Reverse bijection   Laguerre heaps (=multilinear heaps of pointed segments) -- permutations   117   1:07:57
A triangle of bijections   Permutations (inversion tables) -- Dyck tableaux -- tree-like tableaux   124   1:11:56
relation with Dyck tilings   141  1:24:40
Bijection (restricted) Laguerre histories (of the inverse permutation) and Laguerre heaps   142   1:24:53
Contractions in continued fractions   157   1:31:46
correspondence between the valutions (gamma_k) and (b_k, lambda_k)   166   1:33:54
From restricted Laguerre histories to subdivided Laguerre histories  168   1:34:37
the complete commutative diagram of bijections   175   1:35:32
Relation with commutations diagrams and local rules   181   1:35:50
the ultimate commutative diagram of bijections   185   1:36:09
The end   186   1:37:17

Ch 5c the parameter "q".  Interpretation of the 3-parameters distribution of PASEP tableaux (alternative and tree-like) with
Laguerre histories, subdivided Laguerre histories, Dyck tableaux, Laguerre heaps of segments and permutations,
the 5 parameters PASEP intrepretation with staircase tableaux, moments of Askey-Wilson polynomials

March 12, 2018
slides of Ch 5c   (pdf,  33 Mo)                 
video Ch5c: link to Ekalavya  (IMSc Media Center)
video Ch5c: link to YouTube
video Ch5c: link to bilibili
The parameter "q"   2   0:21
 reminding the ultimate commutative diagram of bijections (end of Ch 5b)   3   0:36
another diagram of relations   5-13   1:17
tridiagonal matrices for Polya urns (probability theory)  14   6:33
tridiagonal matrices for priority queues (computer science)   15   7:08
tridiagonal matrices for dictionnary data structures (computer science)   16   7:42
relation tridiagonal matrices and general (formal) orthogonal polynomials   18   8:54
Where are we going ?  19   9:23
relating the q-PASEP algebra and the q-Weyl-Heisenberg algebra   22   12:26
q-analogues, first steps: inversion tables, q-analogues of Hermite histories   23   16:06
the (alpha,beta ; q) analogue of n!   26   20:18
the "philosophy of histories" and its q-analogues   27   21:17
The maj index   30   26:33
proof of the equality of distribution inv (number of inversions) and maj
on an example and using the "philosophy" of histories   32-52   28:12
q-analogues of Hermite histories   53   31:16
an example giving the number of nestings   56-61   33:22
same chord diagram giving the number of crossings   62   35:52
exercise: symmetric distribution of nestings and crossings in chord diagrams   64   36:57
Rook placements (with no empty rows or columns)   65   37:34
bijection rook placements and Hermite histories (with q-analogue)   66-70   37:49
Rook placements   74   41:33
bijection rook placements -- involutions with 2-colored fixed points   76   41:53
The parameter "q" of the PASEP in Laguerre histories   78   44:33
definition of the q-weight of a Laguerre history   81   45:25
expression of this q-weight with patterns (31-2) in permutations   82   46:10
q-Laguerre polynomials I and II defined by their  (b_k, lambda_k)   83   48:25
The parameter "q" of the PASEP (= number of crossings in alternative tableaux)
the "essence" of the parameter (32-1)   84   48:54
from permutations (inversion tables) to Laguerre heaps 92-107   55:03
(change of notation: Laguerre heap = multilinear heap of pointed segments)
expression of the parameter q of the PASEP in term of inversion table of permutations   108   58:54
transporting this parameter q to Laguerre heaps and then to Laguerre histories   109-111   1:00:53
q-subdivided Laguerre histories   112   1:05:36
transporting the parameter q from Laguerre histories to subdivided Laguerre histories   113-116   1:05:41
q-subdivided Laguerre histories with number of nestings (in the pair of Hermite histories)  117   1:06:13
q-subdivided Laguerre histories with number of crossing (in the pair of Hermite histoiries) 118   1:06:18
equivalence with "number of crossings" in the related permutation   119   1:06:39
What about the triple of parameters (alpha, beta, q)   121   1:08:19
the parameter alpha in Laguerre histories   123   1:09:14
transporting the pair (alpha, beta) from alternative tableaux to Laguerre heaps   126-128   1:12:03
the triple distribution (alpha, beta, q) on Laguerre heaps and related permutation   131   1:13:06
the triple distribution (alpha, beta, q) on permutations   (Josuat-Vergès theorem)   132   1:13:38
What about the approach by physicists ?   133   1:14:41
the partition function given by Blythe, Evans, Colaiori, Essler (with matrix ansartz) 135-136  1:15:05
Complements: q-Hermite and q-Laguerre II   138   1:16:17
moments and coefficients lamda_k for q-Hermite II   141   1:16:35
bijective proof for the moment of q-Hermite II   142-148   1:17:20
expression of the "inversion number" of an involution with no fixed points
in term of nestings and crossings   149  1:17:47
a formula relating number of inversions (of a permutation)
with the number of nestings and crossings of the associated pairs of Hermite histories   151   1:19:18
(beta,q)- Laguerre II moments and polynomials   153   1:20:53
The PASEP with 5 parameters   154   1:21:10
Askey-Wilson polynomials: definition   156   1:21:50
3-terms recurrence relation for Askey-Wilson polynomials   157   1:22:27
matrix ansatz for the PASEP with 5 parameters (Uchiyama, Sasamoto, Wadati)   158-161   1:22:51
staircase tableaux: definition  (Corteel, Williams)   162   1:25:07
bijection staircase alternative tableaux -- alternative tableaux  165-169   1:27:24
same bijection restricted to Catalan alternative tableaux with undelying binary trees   170   1:28:42
the number of 2-colored alternative tableaux is 2^n n!, proof  172-173   1:29:08
weight fot the staircase tableaux   176   1:32:17
The Askey-Wilson integral   178   1:35:15
The 'essence" of bijections   192   1:37:45
from Dyck paths to heaps of dimers (in fact semi-pyramids) with violonist G.Duchamp   188   1:39:14
permutation -- Dyck paths -- Laguerre heaps   189-193   1:40:05
reminiscence of the bijection heaps of dimers -- heaps of segments   194   1:40:49
The end 196   1:41:24