The Art of Bijective Combinatorics Part IV
Combinatorial theory of orthogonal polynomials and continued fractions
The Institute of Mathematical Sciences, Chennai, India (January-March 2019)
Lectures related to the course
Laguerre heaps of segments for the PASEP
algebra and combinatorics seminar IISc, Bangalore, March 8, 2019
slides (pdf, 29 Mo)
The PASEP (partially asymmetric exclusion process) is a toy model in the physics of dynamical systems strongly related to the moments of some classical orthogonal polynomials (Hermite, Laguerre, Askey-Wilson). The partition function has been interpreted with various combinatorial objects such as permutations, alternative and tree-like tableaux, etc. We introduce a new one called "Laguerre heaps of segments", which seems to play a central role in the network of bijections relating all these interpretations.
A survey of the combinatorial theory of orthogonal polynomials and continued fractions.
colloquium IISc, Bangalore, March 7, 2019
slides (pdf, 23 Mo)
The theory of orthogonal polynomials started with analytic continued fractions going back to Euler, Gauss, Jacobi, Stieljes ... The combinatorial interpretations started in the late 70's and is a an active research domain. I will give the basis of the theory interpreting the moments of general (formal) orthogonal polynomials, Jacobi continued fractions and Hankel determinants with some families of weighted paths. In a second part I will give some examples of interpretations of classical orthogonal polynomials and of their moments (Hermite, Laguerre, Jacobi, ...) with their connection to theoretical physics.
Proofs without words: the example of the Ramanujan continued fraction
colloquium IMSc, Chennai, February 21, 2019
slides (pdf, 28 Mo)
video link to Ekalavya (IMSc Media Center)
video link to bilibili
Visual proofs of identities were common at the Greek time, such as the Pythagoras theorem. In the same spirit, with the renaissance of combinatorics, visual proofs of much deeper identities become possible. Some identities can be interpreted at the combinatorial level, and the identity is a consequence of the construction a weight preserving bijection between the objects interpreting both sides of the identity.
In this lecture, I will give an example involving the famous and classical Ramanujan continued fraction. The construction is based on the concept of "heaps of pieces",
which gives a spatial interpretation of the commutation monoids introduced by Cartier and Foata in 1969.
Combinatorial aspects of continued frations and applications
Colloque PFAC, "Philippe Flajolet and analytic combinatorics", Paris, 15 December 2011
slides (pdf, 20 Mo)
In his 1980 seminal paper, Philippe Flajolet stated a fundamental theorem interpreting any analytic continued fractions in terms of certain weighted lattice paths (the so-called Motzkin paths). This theory is equivalent to give an interpretation of the moments of any family of orthogonal polynomials in term of these weighted paths. Combining this general statement with some specific bijections between classical combinatorial objects and the so-called "histories" related to weighted Motzkin paths, Flajolet deduce several combinatorial proofs for many continued fraction expansions of well known power series. In particular the classical "Françon-Viennot bijection" between permutations and "Laguerre histories" play a key role and give rise to a combinatorial theory of the Sheffer class of orthogonal polynomials (i.e. Hermite, Laguerre, Charlier, Meixner I and II).
Using Françon's concept of "data histories", a spectacular application of this combinatorial theory of continued fraction has been made by P. Flajolet (with J. Françon and J. Vuillemin) for the evaluation of the integrated cost of data structures subject to arbitrary sequences of insert, delete and search operations. Each classical data structures is related to a classical family of Sheffer type polynomials.
Extensions of the theory has been made by E. Roblet for Padé approximants and T-fractions. Further combinatorial developments have been made more recently by P. Flajolet with E. van Fossen Conrad and R. Bacher for continued fractions expansions of some elliptic functions. Some recent applications are also related to physics with some discrete integrable systems and positivity in cluster algebras involving continued fraction rearrangements (P. Di Francesco and R. Kedem) or the work of J. Bouttier and E. Guitter relating random planar maps and continued fractions. One of the last paper of Philippe (with P. Blasiak) connects continued fractions with the normal ordering of creation-annihilation operators in quantum physics.