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

*Some possible complementary chapters:*

**Chapter 7 Linearization coefficients**

Linearization coefficients of the five Scheffer orthogonal polynlomials, combinatorial interpretation

Linearization coefficiens of q-Hermite, q-Charlier and q-Laguerre polynomials

Combinatorial proof of the Askey-Wilson integral with a product of 4 q-Hermite polynomials

**Chapter 8 Operators, quadratic algebra and orthogonal polynomials**

q-Hermite polynomials and the (Weyl-Heisenberg) quadratic algebra defined by UD = qDU + Id

Rook placements, q-Hermite, operators U,D and Al-Salam--Chihara polynomials

q-Laguerre polynomials and the (PASEP) quadratic algebra defined by DE = qED + E + D

**Chapter 9 Applications and interactions**

The birth and death process in probability theory revisited with the combinatorics of orthogonal polynomials

Computing integrated cost for data structures in computer science:

stack, priority queue, dictionnary, linear list, symbol table

The PASEP model in physics and its matrix ansatz

Orthogonal polynomials and Smith normal form

**Chapter 10 Extensions**

Biorthogonality

L-fractions, extension of the matrix inversion theorem between orthogonal polynomials and inverse (= vertical) polynomials.

multicontinued fractions, T-fractions, tree-like continued fractions, some examples

Combinatorial theory of Padé approximants and P-fractions

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