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)

**Chapter 3**** Continued fractions**

**Chapter 3a**

February 11 , 2019

slides of Ch3a (pdf 40 Mo)

video Ch3a link to YouTube (from IMSc Matsciencechanel Playlist)

Dedication to Philippe Flajolet 3

Arithmetic continued fractions 9

Some ananlytic continued fractions 13

Euler 15-17

Ramanujan 21

Reminding formal power series, formalisation (Part I, Ch1a, 29-46)

Reminding operations on combinatorial objects, formalisation (Part I, Ch1a, 55-62, 63-75)

Analytic continued fraction 54

Jacobi, Stieljes, equivalence with orthogonal polynomials

The fundamental Flajolet Lemma 60

Proof of Flajolet Lemma 67

Continued fractions and orthogonal polynomials 77

Example: Laguerre polynomials and continued fractions 83

Convergents 88

Convergents: linear algebra proof (Part I, Ch1b, 79-91)

Convergents: bijective proof 102

Back to the bijective proof of the inversion formula N_i,j/D (Part I, ch1c, 10-18) 106

Some extensions of the fomula expressing the convergents (of a Jacobi continued fraction) 113

Contraction of continued fractions 118

Some examples 135

secant and tangent numbers, Euler, Genocchi numbers

Complements: elliptic functions 141

Flajolet card for happy new year 2010 160

Sanscrit 161

The end 162

**Chapter 3b**

February 14 , 2019

slides of Ch3b (31 Mo pdf )

video Ch3b link to YouTube (from IMSc Matsciencechanel Playlist)

Reminding Ch 3a 3

Continued fractions: other examples 15

beta-Tchebychev (Narayan numbers) 16

Schröder numbers 21

Polya q-numbers (staircase polygons or parallelogram polyominoes) 26

directed animals 31

Subdivided Laguerre histories 38

Bijection subdivided Laguerre histories -- permutations (A. de Médicis, X.V.) 43

with pairs of Hermite histories

Reverse bijection: from permutations to subdivided Laguerre histories

Contraction of continued fractions 73

From subdivided Laguerre histories to (restricted) Laguerre histories 81

i.e. contraction in Laguerre histories

Combinatorial proof of Euler's continued fraction 91

i.e. Stilejes continued fraction for the generating function of permutations with the parameter beta (number of cycles)

Bijection subdivided Laguerre histories -- Dyck tableaux 96

Dyck tableaux: definition (Aval, Boussicault, Dasse-Hertaut) 97

From restricted Laguerre histories to Laguerre heaps (of segments) 102

From Laguerre heaps to permutations 105

From permutations to Dyck tableaux 111

From Dyck tableaux to subdivided Laguerre histories 124

commutative diagram ! 126

From restricted Laguerre histories to permutations (word notations) 127

second commutative diagram 129

the whole commutative diagram of Ch 3b 132

Laguerre hepas of segments with 12 parameters for the moments (or continued fraction)

Interpretation (of continued fractions) with heaps of monomers and dimers 135

The end 146

Complementary lecture to Chapter 3, (and also to Part II of ABjC):

**"Proofs without words: the example of the Ramanujan continued fraction"**

colloquium IMSc, Chennai, February 21, 2019

slides (pdf, 28 Mo) video link to YouTube (from IMSc Matsciencechanel Playlist)

Abstract: 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.