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

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