• 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 IV
Combinatorial theory of orthogonal polynomials and continued fractions

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

Chapter 1     Paths and moments
Chapter 1a   Tchebychev I and II, Hermite and Laguerre polynomials as matching polynomials of graphs,
sign reversing involution for the linearization coefficients of Hermite and Laguerre polynomials  

 January 14, 2019
slides of Ch1a   (pdf  18 Mo)                
video Ch1a  link to Ekalavya  (IMSc Media Center)
video Ch1a  link to YouTube (from IMSc Matsciencechanel Playlist)
video Ch1a  link to bilibili
Tchebychev polynlomials 1st kind   p.4   2:35
Fibonacci and Tchebychev polynomials   9   11:05
exercise: formula for the coefficients   15   20:03
Pascal triangle and Pingala   16-20   21:12
 Tchebychev polynlomials 2nd kind   21   24:04
Lucas and Tchebychev polynomials   23   25:18
exercise: formula for the coefficients   29   31:55
Matching polynomials of a graph   30   33:31
definition of the matching polynomial   33   34:24

Hermite polynomials (as matching polynomial of the complete graph Kn   35   37:40

Hermite configurations   41   41:06
exercise: formula for the coefficients, 3-terms linear recurrence  44   46:15
Laguerre polynomials   45   48:04
exercise: formula for the coefficients   49   49:39
exercise: 3-terms linear recurrence   50   51:13
(formal) Orthogonal polynomials   51   52:08
definition of a sequence of (formal) orthogonal polynomials   54   56:10
moments of the Tchebychev polynomials   55   58:43
moments of the Hermite and Laguerre polynomials   56   1:00:46
Orthogonality and linearization coefficients of the Hermite polynomials   58   1:05:48
combinatorial interpretation of the linearization coefficients (Hermite)   61   1:09:06
expresssion for the linearization coefficients   67   1:14:22
the sign reversing involution phi   68-71   1:15:44
another "sign-reversing"  proof without explicit construction of an involution   74-75   1:23:05
Orthogonality and linearization coefficients of the Laguerre polynomials   77    1:25:50
 combinatoirial interpretation of the linearization coefficients (Laguerre)   79   1:26:13
The end   81   1:29:05

Chapter 1b   Dyck paths and sign reversing involution for the linearization coefficients for Tchebychev polynomials II,
definition of formal orthogonality, moments and weighted Motzkin paths, Favard's theorem

 January 17, 2019
slides of Ch1b   (pdf  19 Mo)  
video Ch1b link to Ekalavya  (IMSc Media Center)             
video Ch1b  link to YouTube   (from IMSc Matsciencechanel Playlist)
video Ch1b  link to bilibili
Reminding Ch1a   3   0:30
More about linearization coefficients   17   8:39
generalized derangements   20   11:58
derangements   21   12:36
Complements. The power of bijective proof: the Askey-Wilson integral   23   15:24
Askey-Wilson polynomials   29   18:43
The Askey-Wilson integral   31   20:20
 Linearization coefficients and orthogonality. Exemple: Tchebychev 2nd kind   34   24:39
paths: some notations   36   25:27
Dyck path: definition   37   26:31
The "essence" of the fundamental sign-reversing involutions  38   28:12
combinatorial interpretation of the integral of a product of Tchebychev polynomials 2nd kind   39   29:32
proof with the construction of a sign-reversing involution   42-58   33:34
Problem: linearization coefficients for the Tchebychef 1st kind ?   61   51:10
Orthogonal polynomials: some elementary lemma   61   53:07
Moments of some classical orthogonal polynomials   68   1:00:14
Favard's theorem, 3-terms linear recurrence relation and pavages   70   1:04:38
Favard's theorem   77   1:08:56
interpretation of the term linear recurrence with pavages of the segment graph   80-82   1:10:41
Moments and weighted Motzkin paths   83   1:14:46
weighted path: definition   85   1:15:35
weighted Motzkin paths: definition   86   1:16:19
Combinatorial proof of Favard's theorem    90   1:19:10
the main theorem   91   1:19:36
(proof in the next lecture Ch1c)
The end   96

Chapter 1c   Bijective proof of Favard's theorem, the "main theorem", positivity of linearization coefficients with
De Médicis-Stanton's methodology, tridiagonal matrices

slides of Ch1c   (pdf  13 Mo)
video Ch1c link to Ekalavya  (IMSc Media Center)               
video2 Ch1c  (new) link to YouTube  (from IMSc Matsciencechanel Playlist)
video Ch1c link to bilibili
Reminding Ch1b   2  0:24
Combinatorial proof of Favard's theorem: 3-terms recurrence relation implies orthogonality   9   5:52
the main theorem   10   5:58
corollary: Favard's therem   11   7:25
another version of the main theorem   13   8:04
bijective proof of the main theorem   16   10:54
construction of the sign-reversing involution theta 19   14:25
construction of the first sign-reversing involution  theta1   25-42   16:50
the second involution theta2   43   30:57
end of the proof of the main theorem   47   32:07
the "essence" of the fundamental sign-reversing involutions   48-49   33:07
corollary: evaluation of the coefficients b_k and lamda_k   50-52   34:40
A bijective proof for the positivity of linearization coefficients   53   39:32
Askey positivity theorem   55   40:09
de Médicis - Stanton's  theorem   59   40:59
definition of the map psi   60-64   48:38
two lemmae   67   52:41
definition: marked paths   68   53:10
an example of a weighted path   71-74   57:37
end of the proof of the de Médicis - Stanton's  theorem   75   1:01:05
end of the bijective proof of Askey positivity theorem   76-80   1:02:25
Back to the proof of the main theorem   81   1:09:07
comparison between the proof with the sign-reversing involution theta1 and de Médicis-Stanton's theorem   87   1:10:24
Tridiagonal matrices   91   1:12:32
orthogonal polynomials as a determinant   98   1:18:54
The end 99   1:20:14

Chapter 1d   Inverse polynomials, bijective proof of the inversion theorem, inverse relations for Tchebychev I, II,
first steps with the notion of histories: inverse relations for Stirling numbers I, II and Hermite polynomials, paths duality

 January 24, 2019
slides of Ch1d   (pdf   23 Mo) (version 2, with some corrections after the video: slides 21, 25, 127, 130)               
video Ch1d link to Ekalavya  (IMSc Media Center)
video Ch1d  link to YouTube   (from IMSc Matsciencechanel Playlist)
video Ch1d link to bilibili
Reminding Ch1c   3   0:27
Favard paths   18   8:15
Complements: other interpretation of the moments with heaps of monomers and dimers   22   13:11
Inverse polynomials   26   15:24
inverse polynomials: definition   28   16:04
vertical polynomials: definition   30   17:44
the inversion theorem   31   19:23
classical proof   32   20:22
bijective proof   34   23:38
Inverse relations: examples, Tchebychev I and II   37   26:37
some Riordan's inverse relations from "Combinatorial identities" (1968), ch2   38-40   26:51
inverse relations for Tchebychev polynomials 1st kind   42   30:02
nverse relations for Tchebychev polynomials 2nd  kind   45   33:17
Inverse relations: exemples, Stirling numbers I and II   50   37:04
(idea) of histories for Stirling numbers 1st kind: bijection with partitions   52-62   38:32
 (idea) of histories for Stirling numbers 2nd kind: bijection with permutations   64-74   42:55
Inverse relations: examples, symmetric functions   75   47:17
homogeneous (complete) symmetric functions   77-78   48:08
elementary symmetric functions   79-80   49:08
Duality of paths   81   51:40
Inverse relations: examples, Hermite polynomials and two kind of Hermite histories   91   56:07
Hermite histories II   94-103   59:08
Hermite histories I   109-121   1:03:06
Complements: some remarks about q-Hermite polynomials I and II   123   1:08:12
Complements: "beta-analogue" of Tchebychev 2nd kind   126   1:12:50
The end   131   1:18:57