• 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 2    Moments and histories
Chapter 2a

 January  28 , 2019
slides of Ch2a   (pdf 18 Mo )    
video Ch2a  link to Ekalavya  (IMSc Media Center)           
video Ch2a  link to YouTube   (from IMSc Matsciencechanel Playlist)
video Ch2a  link to bilibili
Recalling Chapter 1: paths and moments   3     0:36
first steps with the notion of histories   10     03:27
Orthogonal Sheffer polynomials   15     05:00
the Askey scheme of hypergeometric orthogonal polynomials   16-17     05:15
definition of Sheffer polynomials   18     6:35
characterization of orthogonal Sheffer polynomials  20-21     8:38
Laguerre polynomails (with parameter alpha)   23     16:05
coefficients, exponential generating function, orthogonality  25     16:47
coefficients b_k and lamda_k  and moments of Laguerre polynomials (with parameter alpha)    26     18:12
discussion     20:06
moments n! and  (n+1)!   27     21:43
introduction to the bijection Laguerre histories -- permutations for the 5 Sheffer polynomials   28-31     22:34
Permutations: classic   32     25:17
recalling elementary definitions and bijections (from Part I, Ch4a)   33     25:32
the bijection cycles and  lr-min elements   34-35      26:20
lr-min (left to right minimum elements)   36     27:47
rises, descents of a permutation   38     30:56
geometric thoery of Eulerian polynomials  (D.Foata and M.P.Schützenberger)   39     31:56
exceedances of a permutation   40     32:36
eulerian distribution     41
discussion: correction for p 42     34:53
up-down sequence of a permutation, alternating permutations   43     36:41
sub-excedante functions   44     37:54
inversion table of a permutation   45-46     38:40
iversion table and Stirling numbers   47     41:25
the reverse bijection: from sub-excedante functions to permutations   48     42:56
Laguerre histories and moments of Laguerre polynomials   49     46:56

spliting the valuation b_k lamda_k_ into four weights b'_k, b''_k, a_k, c_k     51-53     49:13
the weight v* of a Motzkin path   54     53:54

Laguerre histories: definition   56     56:11
The FV bijection Laguerre histories -- permutations, description with words  62     1:00:50
Reciprocal bijection: permutations -- Laguerre histories   67     1:08:13
peak, valley, double rise, double descent of a permutation   68     1:08:21
the x-decomposition in a permutation   70     1:11:24
an example  (of the reverse bijection)   73-74     1:15:13
about the pattern (31-2)   75     1:18:36
The end 76     1:23:49

Chapter 2b

 January  31 , 2019
slides of Ch2b   (pdf 28 Mo )                
video Ch2b  link to Ekalavya  (IMSc Media Center)
video Ch2b  link to YouTube   (from IMSc Matsciencechanel Playlist)
video Ch2b  link to bilibili
Reminding Ch2a   3     00:43
The bijection Laguerre histories -- permutations described with words
Weighted Laguerre histories   9       06:01
the parameter alpha as lr-max elements   13     08:45
initial elements in a permutation   17     16:39
exercise: characterization of lr-min elements  18     18:20
discussion: lr-min elements, outstanding elements, average cost in computer science, harmonic number, ...   20:37
Restricted Laguerre histories   19     22:18
definition: restricted Laguerre histories   20     23:08
the parameter beta as lr-min elements   21     25:26
(large) Laguerre histories and restrictred Laguerre histories: summary  22-23      28:34
the FV bijection Laguerre histories -- permutations, description with binary trees   24     30:04
binary trees: recalling main notions ( from Part I, Ch2a)   25
anecdot about the choice between words or binary trees notations   25-26     30:35
definition: binary trees   26     32:06
Catalan numbers   27     33:14
bijection binary trees -- complete binary trees  28-30     33:22
subtrees   32     34:46
double vertex, (right, left) simple vertex, leaf  33     35:11
left and right principal branch of a binary tree   34     35:39
inorder (or symmetric order)   35-36     36:03
Increasing binary trees  (from PartI, Ch2a)  37     37:10
definition: increasing binary tree   38     37:26
definition: projection of an increasing binary tree   38     38:50
"déployé" of a word and the reverse bijection permutation -- increasing binary trees   39     40:14
an example   40-44     42:37
definition: x-factorization   45     43:28
Corollary: relation valley, peak, double rise, double descent -- double vertex, leaf, right and left simple vertex  46     46:21
relation lr-min, rl-min elements and left, right principal branches in increasing binary trees   48     49:40
The bijection Laguerre histories -- permutations, description with increasing binary trees   52     51:45
description of the bijection Laguerre histories -- increasing permutations   54-62      51:59
comparison of the two descriptions of the FV bijection   64-72     53:40
Orthogonal Sheffer polynomials   75     54:41
recalling definition and characterization (from Ch1a)   76-77     54:45
recalling the five orthogonal Sheffer polynomials   78-80     55:36
Charlier histories   81     57:10
Charlier polynomials: coefficients, exponential generating function, orthogonality  82     57:19
Charlier polynomials: coefficients b_k and lamda_k, moments   83     58:05
Charlier histories: definition   84     59:14
Charlier histories: an example   85-94     1:00:31
Hermite histories   95     1:05:03
Moments of Meixner polynomials   98     1:06:48
coefficients, exponential generating function, orthogonality  99     1:07:01
coefficients b_k and lamda_k    100     1:07:42
spliting the coefficients b_k and lamda_k for a combinatorial interpretation of the moments   101     1:09:24
Eulerian polynomials and explicit expression for the moments   102-103     1:12:27
particular case: Meixner-Kreweras polynomials and ordered partitions   105     1:15:12
Moments of the Meixner-Pollaczek polynomials   106     1:17:20
exponential generating function, orthogonality   107     1:17:31
coefficients b_k and lamda_k    108     1:18:07
combinatorial interpretations of the moments 109-110     1:20:04
discussion about the parameters s(sigma), v(simgma) and symmetries of permutations    111     1:22:33
special case with Euler (or secant) numbers and alternating permutations   112-113     1:26:01
Table for the moments of the five Sheffer polynomials   114     1:27:03
Moments for the general formal Sheffer orthogonal polynomials   119     1:27:35
interpretation of these moments permutations with 6 parameters   121-123     1:28:07
The end   124     1:31:09

Chapter 2c

 February 4, 2019
slides of Ch2c   (v2, pdf 24 Mo )                
video Ch2c  link to Ekalavya  (IMSc Media Center)
video Ch2c  link to YouTube   (from IMSc Matsciencechanel Playlist)
video Ch2c  link to bilibili
Reminding Ch2b   3     00:30
Closure of histories   20     10:12
Closure of the (open) history (with Motzkin paths) for set partitions (Ch1d)   26     18:14
Closure of the (open) history (with Favard paths) for permutations (Ch1d)   38     23:28
Moments for the general formal Sheffer orthogonal polynomials   57
interpretation of these moments with permutations in "cycles notation" with 6 parameters   58     35:09
The two bijections restricted Laguere histories -- permutations (in "word notation" and in "cycles notation") acting in parallel   59     36:15
Back to an exercise of Ch2b (histories for Meixner-Kreweras moments)   76      39:20
The origin of the notion of histories:
computer science, data structures and histories   78     41:45
Example: binary search tres, analysis of algorithms   79      42:49
average cost of an insertion in a binary search tree   86     45:08
relation binary search tree and increasing binary tree   87     45:58
Data structures and histories: integrated cost   88     47:23
dictionnary data structure   89     47:35
the idea of integratrd cost of a data structure
Françon's "histoire de fichiers" (data structure histories)   90     51:10
Priority queue   91     
Representation of an history for the data structure "dictionnary" (with a Laguerre heap of segments)   95     53:19
Laguerre heaps of segments: reminding the notion of heaps of pieces, (ABjC Part II)    105     58:20
heaps of pieces: definition   109-110     59:15
the example of heaps of segments   111     1:01:04
Laguerre heap (of pointed segments): definition   114     1:03:12
Laguerre heap: an example   114     1:06:04
Bijection Laguerre heaps -- (restricted) Laguerre histories -- permutations    116     1:07:32
bijection Laguerre heaps -- (restricted) Laguerre histories: description on an exemple  119-132     1:08:59
the trilogy: Laguerre heaps -- (restricted) Laguerre histories -- permutations   133     1:13:02
3 implementations of restricted Laguerre histories: word and cycle notations, heaps and preheaps  (explanation with the hands)   1:17:31
Moments for the general formal Sheffer orthogonal polynomials with 6 parameters:   
word  notation   134     1:19:04
cycle notation   135     1:19:26
interpretation of these moments with Laguerre heaps with 6 parameters   136     1:19:44
interpretation of these moments with Laguerre heaps with 8 (even 12)  parameters   136-139     1:22:15
Conclusion: relation with the PASEP   (ABjC Part III)   140     1:25:08
The end 145     1:26:41