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