XAVIER VIENNOT
  • PART I
    • abstract
    • contents
    • Ch0 Introduction to the course
    • Ch1 Ordinary generating functions
    • Ch2 The Catalan garden
    • Ch3 Exponential structures and genarating functions
    • Ch4 The n! garden
    • Ch5 Tilings, determinants and non-intersecting paths
    • list of bijections
    • index
  • PART II
    • abstract
    • contents
    • Ch1 Commutations and heaps of pieces: basic definitions
    • Ch2 Generating functions of heaps of pieces
    • Ch3 Heaps and paths, flows and rearrangements monoids
    • Ch4 Linear algebra revisited with heaps of pieces
    • Ch5 Heaps and algebraic graph theory
    • Ch6 Heaps and Coxeter groups
    • Ch7 Heaps in statistical mechanics
    • Some lectures related to the course
  • PART III
    • abstract
    • contents
    • Ch0 overview of the course
    • Ch1 RSK The Robinson-Schensted-Knuth correspondence
    • Ch2 Quadratic algebra, Q-tableaux and planar automata
    • Ch3 Tableaux for the PASEP quadratic algebra
    • Ch4 Trees and tableaux
    • Ch5 Tableaux and orthogonal polynomials
    • Ch6 Extensions: tableaux for the 2-PASEP quadratic algebra
    • Lectures related to the course
    • references, comments and historical notes
  • PART IV
    • introduction
    • contents
    • Ch0 Overview of the course
    • Ch1 Paths and moments
    • Ch2 Moments and histories
    • Ch3 Continued fractions
    • Ch4 Computation of the coefficients b(k) lambda(k)
    • Ch5 Orthogonality and exponential structures
    • Ch6 q-analogues
    • Lectures related to the course
    • Complements
    • references
  • Epilogue

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