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 

Introduction

From the first edition (1938) of the classical book of Gabor Szegö « Orthogonal polynomials »:
Recent years have seen a great deal of progress in the field of orthogonal polynomials, a subject closely related to many important branches of analysis. Orthogonal polynomials 
are connected with trigonometric, hypergeometric, Bessel, and elliptic functions, are related to the theory of continued fractions and to important problems of interpolation 
and mechanical quadrature, and are of occasional occurrence in the theories of differential and integral equations. In addition, they furnish comparatively general and instructive illustrations of certain situations in the theory of orthogonal systems. Recently, some of these polynomials have been shown to be of significance in quantum mechanics and in mathematical statistics. 
The origins of the subject are to be found in the investigation of a certain type of continued fractions, bearing the name of Stieltjes. Special cases of these fractions were studied by Gauss, Jacobi, Christoffel, and Mehler, among others, while more general aspects of their theory were given by Tchebichef, Heine, Stieltjes, and A. Markoff. 
Despite the close relationship between continued fractions and the problem of moments, and notwithstanding recent important advances in this latter subject, continued fractions have been gradually abandoned as a starting point for the theory of orthogonal polynomials. 
As mentioned in further editions of Szegö's book (1958, 1966, 1975), considerable progress has been made in the field of orthogonal polynomials, with many interactions in various fields such as numerical analysis, quantum and statistical physics, probabilities theory. The theory of orthogonal polynomials was considered as part of analysis, until the late 70's and early 80's when some combinatorists gave combinatorial interpretations of some classical orthogonal polynomials (Hermite, Laguerre, Jacobi, ...) and reproved in a combinatorial way with bijections some identities related to these polynomials such as Mehler identity for Hermite polynomials. Also was discovered combinatorial interpretations of the so-called linearization coefficients (Integral of a product of orthogonal polynomials), giving a proof of some positivity of these coefficients. The combinatorics behind these classical polynomials appears to be exponential structures (see part I, ch3 of the present course).
Another type of combinatorial approach appears in 1980 with the seminal paper of Flajolet giving a combinatorial interpretation of Jacobi and Stieljes (analytic) continued fraction in terms of weighted Motzkin and Dyck paths. This was the starting point for a combinatorial theory of general orthogonal polynomials given in 1983 by the speaker. Large parts of the classical analytic theory can be completely rewritten in terms of combinatorial objects and bijective proofs. The orthogonality is no more defined in terms of an integral with a measure on the real numbers, but with a linear functional on the space of polynomials, which can be defined by a sequence of moments. This is the point of view developed in the book of Theodore Chihara "an introduction to orthogonal polynomials", (1978, reprint 2011) where orthogonality is defined in such formal way. 
It appears that the moments of some classical orthogonal polynomials are some well known sequences of combinatorics enumerating classical objects such as permutations, set partitions, involutions with no fixed point. When a family of orthogonal polynomials involve some parameters, these parameters considered as real or complex numbers in the classical (analytic) theory of orthogonal polynomials are now considered as formal variables, which will correspond to some (classical) parameters in the associated combinatorial model. 
In parallel with the notion of weighted Motzkin paths, a key concept is the notion of histories introduced by Françon in relation with data structures in computer science. A fundamental bijection introduced by Françon and the speaker in 1978 is between permutations and the so-called Laguerre histories. A consequence is to give complete combinatorial interpretation of the moments of five classical families of orthogonal polynomials: Hermite, Charlier, Laguerre, Meixner and Meixner-Pollaczek. Such polynomials are exactly the five possible families which are orthogonal and Scheffer type.
It is a surprise that some bijections introduced to prove some classical results of orthogonal polynomials theory, are very closed each other, although they proves completely different results, such as for example:  the proof of orthogonality (sufficient condition of classical Favard's theorem), inversion of the matrix of coefficients of orthogonal polynomials (in Chapter 1), expression of the convergent of a Jacobi continued fractions as ratio of orthogonal polynomials (chapter 3), Ramanujan's algorithm for expanding a power series into continued fraction (chapter 4). An interest of such bijective proofs of (very) classical results is that the proof can be easily extended to some sequence which are no more orthogonal sequence. For example the inversion theorem of chapter 1 can be extended to any sequence of polynomials, see chapter 10 with Lukasiewicz paths and the corresponding L-fractions.

With the combinatorial formulation of the theory of orthogonal polynomails, a kind of duality appears in many part of this course and take different forms: it can be the inversion matrix theorem of chapter 1( between the matrix of coefficients of orthogonal polynomials and the matrix of weigthed Motzkin paths reaching an arbitrary level), the duality of paths (Favard and Motzkin) appearing in the context of the Hankel determinants of chapter 4 with particular examples giving the duality between the two kind of Striling numbers or the duality between elementary and homogenous symmetric functions. When the theory in formulated (chapter 3) in terms of heaps of pieces (monomers and dimers) exposed in part II of this course, then the duality is the inversion theorem relating trivial heaps (= orthogonal polynomials) and heaps (= convergents of Jacobi continued fractions). In chapter 5 about orthogonal Scheffer polynomials, this duality is between the exponential generating function for the orthogonal polynomials and the corresponding delta operator expressed in terms of histories, and the duality becomes the Lagrange inversion formula of power series.

This combinatorial approach for orthogonal polynomials has been very fruitful for applications and interactions. For example in computer science in the early 80's the notion of histories associated to the combinatorics of the moments of orthogonal polynomials leads to the computation of integrated cost for data structures such as stack, priority queue, dictionnary, symbol table, linear list. To each of these data structures correspond classical orthogonal polynomials, here respectively Tchebychef, Hermite, Laguerre, Charlier and some Meixner polynomials. Let's mention the numerous papers published in the last 15 years on the combinatorics of the PASEP (partially asymmetric exclusion process) model, a toy model in the physics of dynamical systems far from equilibrium. In a reverse way, the computation by physicists of the stationary probabilities of the most general model with 5 parameters inspired combinatorists in order to give a combinatorial interpretation of the moments of the Askey-Wilson polynomials, polynomials which are the top of the classification of "classical" orthogonal polynomials (the famous Askey scheme). In this approach the moments are interpreted by some families of "tableaux" (called permutation, alternative, tree-like and staircase tableaux). See part iII of this bijective course.
This course gives an original way to learn the classical (at least some parts of the formal) theory of orthogonal polynomials, together with some chapters of bijective combinatorics. No prerequisites is required in analysis or in combinatorics, just some elementary notions in linear algebra (matrix, determinant, linear form, ...) and in combinatoircs such as formal power series (generating functions), permutations, binary trees, paths, .... This course is the fourth part of "The Art of Bijective Combinatorics" and can be followed independently from the 3 first parts. Some overlaps appear.
Isle-Saint-Georges,
22 November 2018

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

contents of the course
references
Some preliminary versions of this course is available on my "old" website   www.xavierviennot.org
 see  the slides (mostly in english)  of the  "petite école" I gave in 2006/2007 at the combinatorial group of LaBRI, Bordeaux
"Une théorie combinatoire des polynômes orthogonaux, ses extensions, interactions et applications"
and the Lecture Notes (in french), UQAM, Montréal, 1984,  is available   here