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
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
Lectures related to the course
The playlist from matsciencechannel of the videos of this course is here