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)

**Preface**

** **

This is part IV of the so-called "video-book" "The Art of Bijective Combinatorics" ("ABjC" for short). It is based on a course given in 2019 at The Institute of Mathematical Science (IMSc), Chennai, India, at the invitation of Amritanshu Prasad (Amri).

**Analogously to the other Parts of ABjC, there are 3 components:**

- a set of 19 lectures video-recorded available on YouTube, Ekalavya (the IMSc Media Center in India) and the Chinese chain bilibili

- the corresponding set of slides of each lecture,

- this website which enable one to navigate inside the videos, in the same way you turn around the pages of a book. For example if you click on the time given just after the slide number corresponding to one of the videos, you will get, up to one second, to exact position in the video.

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

**Part IV of ABjC is based on the seminal paper**

- Philippe Flajolet (1980) Combinatorial aspects of continued fractions. Discrete Math., 32), 125–161,

**and the monograph** (in French)

- X.G. Viennot (1983) Une théorie combinatoire des polynômes orthogonaux généraux. Lecture Notes, UQAM, (Université du Québec à Montréal), 219 pp. (pdf, 29Mo)

Since these works, many developments appeared until today (2020) in the literature. It is the aim of this volume iV to make available for non French speaking readers the monograph of 1983, together with some more recent developments we consider of general interest in the vein of this combinatorial approach to orthogonal polynomials.

In particular in the last 15 years there have been an intensive activity around the combinatorial approach to the PASEP model in the physics of dynamical systems far from equilibrium (PASEP = partially asymmetric exclusion model). This combinatorial approach is described in details in Part III of ABjC and Chapter 5 of Part III is devoted to the relation between the PASEP and orthogonal polynomials. This relation is in the spirit of the combinatorial approach described here in this Part IV.

We had in mind 10 chapters for this course. Whithin the 24 hours of a course at IMSc we gave the first 6 chapters. The four others are described here.

**A course at two different levels**

I gave this coursesat two different levels at the same time. Most of the courses are supposed to be followed by good undergraduate students (at the Master level) and graduate students. I also gave some more advanced topics, opening some «windows» without proof, for graduate students, researchers and professors, in connection with active researches in combinatorics, and sometimes with connection in theoretical physics and computer science. Such sections are listed under the name «*Complements*».

**How to quote this video-book in the literature**

The videos, slides and the address of this video-book ABjC will remain unchanged. It is possible to quote this video-book in the literature in the same way as quoting a book. If you give only the direct link to a set of slides, or to the YouTube address of a video, the reader will miss the corresponding page giving the precise decription of the slides, video and direct links in order to navigate inside the video. Also think of our Chinese colleagues, for which the link to the video is only through the popular Chinese chain "bilibili".

I suggest the following:

- if you want to quote this volume of ABjC, I suggest to quote in an analoguous way to a book, with the editor (here IMSc), the place of edition (here Chennai) and the year, for example:

*The Art of Bijective Combinatorics*, Part IV, *A combinarial theory of orthogonal polynomials and continued fractions* IMSc, Chennai, 2019, http://www.viennot.org/abjc4.html

the pointer is going to this web page (Preface of Part IV of ABjC), the reader will also get access to the scaner version of X.V. 1983 Lecture Notes at UQAM.

- if you want to quote a precise point inside the video-book, as for example a definition, theorem or bijection, I suggest to refer to the number(s) of the corresponding slide(s). Example: the beautiful bijective proof by D. Stanton and A. de Médicis for the positivity of some linearization coefficients (Askey's theorem)

*The Art of Bijective Combinatorics*, Part IV, Chapter 1c, IMSc, Chennai, 2019, pp 53-80, http://www.viennot.org/abjc4-ch1.html

the suffix abjc4-ch1.html refers to the web page of Chapter 1 of Part "IV" of ABjC, this page containing the different slides and videos of the 3 lectures Ch1a, Ch1b and Ch1c corresponding to Chapter 1.

- if you want to quote the whole collection of the 4 volumes then:

*The Art of Bijective Combinatorics*, IMSc, Chennai, 2016-2019, http://www.viennot.org/abjc.html

the suffix /abjc.html refers to the web page of the (general) preface of ABjC.

**Duality of paths**

between Motzkin paths

(moments)

and

Favard paths

(3 terms linear recurrence)

from the cover page of the 1983 monograph

[Fig. 12, p I V- 26]