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 4**** Expanding a power series into continued fraction**

(equivalently computation of the coefficients b(k) and lambda(k))

**Chapter 4a**

February 18, 2019

slides of Ch4a (pdf 31 Mo)

video Ch4a link to YouTube (from IMSc Matsciencechanel Playlist)

A direct algorithm with Motkin paths: 4

form the momenrts mu(n) to the coefficients b(k) and lambda(k)

Hankel determinants 9

definition, Toeplitz matrix

The LGV Lemma (part I, Ch 5a, 3-28) 12

the LGV Lemma (general form) 23

the LGV Lemma (classical form, with the corssing condition) 25

A simple example 28

Fermat matrix of binomial coefficients

About the terminology LGV Lemma 32

proofs fromTHE BOOK, what is a *Lemma ?*, C.Krattenthaler' comments

Orthogonal polynomials (or Jacobi continued fractions):

computing the coefficients b(k) and lambda(k) with Hankel determinants of moments 38

the Hankel determinant Delta_n 45

formula for the coefficient lambda(n) in terms of Delta_n determinants 49

existence of sequence of orthogonal polynomials for a sequence of moments 51

the Hankel determinant Khi_n 54

formula for the coefficient b(n) 56

Orthogonal polynomials (or Stieljes continued fractions):

computing the coefficients lambda(k) with Hankel determinants of moments 57

the Hankel determinants Delta0_n and Delta1_n 60

formlula for the coefficiens lambda(2n) and lambda(2n+1) 69

existence of orthogonal polynomials from the moments sequence mu(2n)=nu(n) and mu(2n=1)=0 71

a classical determinant formula for orthogonal polynomials 73

duality between Favard paths and Motzkin paths

the determinant formula 90

Duality (the idea of duality of paths) 91

(part I, Ch 5b, 32-41)

Complements: inverse power series 103

Colmmplements: some Hankel determinants 111

Hankel determinants for Aztec tilings 113

(see Part I, Ch 5b, 87-113)

"Bijective computation" of the Hankel determinant of Schröder numbers giving the number of tilings of the Aztec diagram 127

Another Hankel determinant 136

perfect matching of some pentagons-hexqagons graph (de Sainte-Catherine, X.V.) 138

Hankel determinant of Catalan numbers 140

A festival of bijections 142-150 (epilogue of Part I, end of Ch 5b)

The end 152

**Chapter 4b**

February 21 , 2019

slides of Ch4b (pdf 28 Mo)

video Ch4b link to YouTube (from IMSc Matsciencechanel Playlist)

Reminding Ch 4a 4

Ramanujan's algorithm 13

Ramanujan's formula as written in his Notebook (chapter 12, entry 17) 14-16

Ramanujan's formula restated with pavages and weighted Dyck paths 19

bijective proof of Ramanujan's formula 20-27

Other proofs of Ramanujan's formula 29

Goulden-Jackson's formula 31

bijective proof of Goulden-Jackson's formula 36-41

The quotient-difference algorithm 46

description of the qd-algorithm 52-56

the rhombus rules 56

3 examples: Catalan numbers, n!, 1. 3 ... (2n-1) 57-59

the qd-transform 60

definition of the qd-transform (of a sequence) 61

4 examples of the qd-transform 62-65

characterization of the qd-transform 66

Proof (of the characterizaton of the qd-transform) 69

Combinatorial proof for the quotient-difference (qd-) algorithm 76

Expression with Hankel determinant 86

Complexity of the algorithm, direct algorithm with Motzkin paths 94

Combinatorial applications 100

qd-table for the Catalan numbers 107

The idea of compression of paths for configurartions of non-crossing paths 111

An idea for a research problem 122

The end 127