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 YouTube (from IMSc Matsciencechanel Playlist)
Recalling Chapter 1: paths and moments 3
first steps with the notion of histories 10
Orthogonal Sheffer polynomials 15
the Askey scheme of hypergeometric orthogonal polynomials 16-17
definition of Sheffer polynomials 18
characterization of orthogonal Sheffer polynomials 20-21
Laguerre polynomails (with parameter alpha) 23
coefficients, exponential generating function, orthogonality 82
coefficients b_k and lamda_k 83
Permutations: classic 32
recalling elementary definitions and bijections (from Part I, Ch4a)
the bijection cycles and lr-min elements 35
lr-min (left to right minimum elements) 36
rises, descents of a permutation 38
geometric thoery of Eulerian polynomials (D.Foata and M.P.Schützenberger) 39
exceedances of a permutation 40
up-down sequence of a permutation 43
sub-excedante functions 44
inversion table of a permutation 46
the reverse bijection: from sub-excedante functions to permutations 48
Laguerre histories and moments of Laguerre polynomials 49
spliting the valuation b_k lamda_k_ into four weights b'_k, b''_k, a_k, c_k
Laguerre histories: definition 56
The FV bijection Laguerre histories -- permutations, description with words 62
Reciprocal bijection: permutations -- Laguerre histories 87
peak, valley, double rise, double descent of a permutation 68
the x-decomposition in a permutation 70
about the pattern (31-2) 75
The end 76
Chapter 2b
January 31 , 2019
slides of Ch2b (pdf 28 Mo )
video Ch2b link to YouTube (from IMSc Matsciencechanel Playlist)
Reminding Ch2a 3
The bijection Laguerre histories -- permutations described with words
Weighted Laguerre histories 9
the parameter alpha as lr-max elements 13
initial elements in a permutation 17
Restricted Laguerre histories 19
the FV bijection Laguerre histories -- permutations, description with binary trees 24
binary trees: recalling main notions ( from Part I, Ch2a) 25
definition, Catalan numbers,
bijection binary trees -- complete binary trees 28
double vertex, (right, left) simple vertex, leaf 23
left and right principal branch of a binary tree 34
inorder (or symmetric order) 35
Increasing binary trees (from PartI, Ch2a) 37
definition, projection of an increasing binary tree 38
"déployé" of a word and the reverse bijection permutation -- increasing binary trees 39
x-factorization 45
relation lr-min, rl-min elements and left, right principal branches in increasing binary trees 50
The bijection Laguerre histories -- permutations, description with increasing binary trees 52
description of the bijection Laguerre histories -- increasing permutations 54-62
comparison of the two descriptions of the FV bijection 64-72
Orthogonal Sheffer polynomials 75
recalling definition and characterization (from Ch1a) 76-77
Charlier histories 81
coefficients, exponential generating function, orthogonality, coefficients b_k and lamda_k 82
Hermite histories 95
Moments of Meixner polynomials 98
coefficients, exponential generating function, orthogonality 99
coefficients b_k and lamda_k 100
combinatorial interpretation of the moments 102
Eulerian polynomials and explicit expression for the moments 103
particular case: Meixner-Kreweras polynomials and ordered partitions 105
Moments of the Meixner-Pollaczek polynomials 108
exponential generating function, orthogonality 107
coefficients b_k and lamda_k 108
combinatorial interpretations of the moments 110
special case with Euler (or secant) numbers and alternating permutations 112
Table for the moments of the five Sheffer polynomials 114
Moments for the general formal Sheffer orthogonal polynomials 119
interpretation of these moments permutations in "words notation" with 6 parameters 121
The end 124
Chapter 2c
February 4, 2019
slides of Ch2c (v2, pdf 24 Mo )
video Ch2c link to YouTube (from IMSc Matsciencechanel Playlist)
Reminding Ch2b 3
Closure of histories 20
Closure of the (open) history (with Motzkin paths) for set partitions (Ch1d) 26
Closure of the (open) history (with Favard paths) for permutations (Ch1d) 38
Moments for the general formal Sheffer orthogonal polynomials
interpretation of these moments with permutations in "cycles notation" with 6 parameters 58
The two bijections restricted Laguere histories -- permutations (in "word notation" and in "cycles notation") acting in parallel 59
Back to an exercise of Ch2b (histories for Meixner-Kreweras moments) 76
The origin of the notion of histories:
computer science, data structures and histories 78
Example: binary search tres, analysis of algorithms 79
Data structures and histories: integrated cost 88
Representaion of an history for the data structure "dictionnary" 95
Laguerre heaps of segments: reminding the notion of heaps of pieces, (ABjC Part II)
heaps of pieces: definition 110
the example of heaps of segments 111
Laguerre heap (of pointed segments): definition 114
Bijection Laguerre heaps -- (restricted) Laguerre histories -- permutations 116
description on an exemple 119-133
Moments for the general formal Sheffer orthogonal polynomials
interpretation of these moments with Laguerre heaps with 8 parameters 136
Conclusion: relation with the PASEP (ABjC Part III) 140
The end 145