XAVIER VIENNOT
  • PART I
    • 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
    • list of bijections
    • index
  • PART II
    • 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
    • Some lectures related to the course
  • PART III
    • 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
    • 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

A combinatorial theory of orthogonal polynomials and continued fractions

 

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

Monday and Thursday, 11h30-13h, video room, first class (Ch0): 10th January 2019

A mirror image of this website is here at IMSc , the Institute of Maths Science at Chennai, India 

Contents

Introduction

 

Chapter 0   overview of the course

 

Chapter 1    Paths and moments

Examples of orthogonal polynomials: Tchebychef, Hermite, Laguerre

Tchebychef (1st and 2nd kind), Hermite and Laguerre polynomials as matching polynomials of graphs

An introduction to bijective proof with sign reversing involution: linearization coefficients for Hermite, Laguerre and Tchebychef polynomials

(formal) orthogonal polynomials: definition, moments

Pavages and 3-terms linear recurrence, Favard paths

Moments as weighted Motzkin paths

Tridiagonal matrices, expression of orthogonal polynomias as determinants

Combinatorial (bijective) proof: 3-terms recurrence implies orthogonality

Combinatorial (bijective) proof for the inverse polynomials

Application of such bijective proofs for the positivity of some linearization coefficients

 

Chapter 2   Moments and histories

Hermite histories, bijection with involutions with no fixed points

Laguerre histories: definition

Bijection permutations -- Laguerre histories in terms of increasing binary trees

Bijection permutations -- Laguerre histories in terms of words

Properties of the bijection permutations -- Laguerre histories

Restricrted Laguerre histories

Second bijection permutations -- retricted Laguerre histories (with cycles notation)

The five classes of orthogonal Scheffer polynomials: Hermite, Charlier, Laguerre, Meixner, Meixner-Pollaczeck

Combinatorial interpretation of the moments of the five orthogonal Scheffer polynomials

 

Chapter 3   Continued fractions

introduction: arithmetic and analytic contined fractions

Jacobi and Stieljes continued fractions, combinatorial interpretations with weighted Motzkin paths

Convergents and orthogonal polynomials, bijective proof

Contractions in paths and in continued fractions

Examples of contractions: permutations and subdiveded Laguerre histories

Examples of continnued fractions: Narayana numbers, Schröder numbers, staircase polygons, tangent numbers, Genocchi numbers, elliptic functions, ...

Ramanujan continued fraction

Interpratation of continued fractions with heaps of monomers and dimers

 

Chapter 4  Computations of the coefficients ot the 3-terms recurrence relation

(equivalently: expanding a power series into Jacobi continued fraction)

Direct algorithm (from the Motzkin paths)

Hankel determinants

The LGV Lemma with non-intersecting paths

Interpretation of Hankel determinants of moments with configurations of Dyck paths and Motzkin paths

Total positivity of Hankel matrices

Expression of the coefficients of the 3-terms recurrence relation with Hankel determinants of moments

Duality of paths with Favard and Motzkin paths

Examples of Hankel determinants: Catalan numbers, inverse power series

The quotient-difference algorithm (qd-algorithm), definition, examples, combinatorial interpretation

Back to the Hankel determinants of Catalan numbers

Ramanujan algorithm for expanding continued fraction, definition, combinatorial interpretation, bijective proof

 

Chapter 5   Orthogonality and exponential structures

back to chapter 3, part I, species and exponential structures

Hermite and Laguerre configurations

Combinatorial proof of Mehler identity for Hermite polynomials

interpretation of Jacobi polynomials

Scheffer and binomial type polynomials, characterization, delta operator, introduction to Rota umbral calculus

The five classes of Scheffer orthogonal polynomials: Hermite, Charlier, Laguerre, Meixner, Meixner-Pollaczeck

Five interpretations for the corresponding S and Q delta operators

 

Chapter 6    q-analogues 

Two q-Hermite polynomials and q-Hermite histories

Two q-Laguerre polynomials, q-Laguerre histories and subdivided q-Laguerre histories

q-Charlier polynomials and q-Charlier histories

Al-Salam--Chihara polynomials, Askey-Wilson polynomials

 

Epilogue

 

Lectures related to the course

 

Complements 

 

References

 

 The  playlist from matsciencechannel of the videos of this course is here