• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • 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
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • 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
    • Lectures related to the course
  • PART III
    • Preface
    • 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
    • Preface
    • 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 Ekalavya  (IMSc Media Center)
video Ch4a  link to YouTube (from IMSc Matsciencechanel Playlist)
video Ch4a  link to bilibili
A direct algorithm with Motkin paths:   

form the momenrts mu(n) to the coefficients b(k) and lambda(k)   5     01:25

Hankel determinants   9     06:21
definition, Toeplitz matrix
The LGV Lemma  (part I, Ch 5a, 3-28)   12     07:47
the LGV Lemma (general form)   17     11:21
the crossing condition   24     16:05
the LGV Lemma (classical form, with the corssing condition)  25     17:16
A simple example   28     18:40
Fermat matrix of binomial coefficients   
About the terminology LGV Lemma   32     20:58
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     23:50
lemma: interpretation of a general Hankel determinant of moments   40     25:03
an example with Motzkkin paths and virtual crossing   41     26:30
2 examples with Dyck paths   43-44     28:14
discussion   29:04
the Hankel determinant Delta_n   45     30:24
formula for the coefficient lambda(n) in terms of Delta_n determinants   49     32:54

proposition: existence of sequence of orthogonal polynomials for a sequence of moments   51     33:41
the Hankel determinant Khi_n   54     37:20
formula for the coefficient b(n)  56     39:01
Orthogonal polynomials (or Stieljes continued fractions):
computing the coefficients lambda(k) with Hankel determinants of moments  57    40:34
the Hankel determinants Delta0_n and Delta1_n   61     41:31
formlula for the coefficiens lambda(2n) and lambda(2n+1)   69     44:28
existence of orthogonal polynomials from the moments sequence mu(2n)=nu(n) and mu(2n=1)=0   71     45:36
a classical determinant formula for orthogonal polynomials   73     47:19
the determinant formula     74     47:36

slides corrected:  74,75, 76 corrections for the expression of  a_n,p

duality between Favard paths and Motzkin paths     81-87     54:53
corrections for the slides 89,90 (about the weight v(beta))

some discussion  (corrections for the expression of  a_n,p the weight v(beta))      58:20

the determinant formula     93     1:01:39
Duality (the idea of duality of paths)   94     1:02:50
(part I, Ch 5b, 32-41) [some problems with the sound]
Complements: inverse power series   103     1:06:41
Complements: some Hankel determinants   111     1:11:59
Hankel determinants for Aztec tilings  121     1:14:32
(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   130     1:16:45
Another Hankel determinant   139     1:18:49
perfect matching of some pentagons-hexqagons graph (de Sainte-Catherine, X.V.)   141     1:19:25
Hankel determinant of Catalan numbers   143     1:20:04
A festival of bijections   145-153  (epilogue of Part I, end of Ch 5b)     1:20:28
The end   155     1:22:18

Chapter 4b

February  21 , 2019
slides of Ch4b   (pdf 28 Mo)                
video Ch4b  link to Ekalavya  (IMSc Media Center)
video Ch4b  link to YouTube (from IMSc Matsciencechanel Playlist)
video Ch4b  link to bilibili
Reminding Ch 4a   4     00:44
Ramanujan's algorithm   13     03:33
Ramanujan's formula as written in his Notebook (chapter 12, entry 17)  14-16     03:39
Ramanujan's formula with the notation of the course   17     08:13
Ramanujan's formula restated with pavages and weighted Dyck paths   19     10:11
bijective proof of Ramanujan's formula (with a weight preserving sign-reversing involution)   20-27     11:47
a variation of Ramanujan's formula   28     22:13
Other proofs of Ramanujan's formula   29     23:09
Berndt, Lamphere, Wilson; Goulden-Jackson; Andews;   30
Goulden-Jackson's formula  31     24:19
bijective proof of Goulden-Jackson's formula   36-41     27:33
same 'essence' of various weight preserving sign-reversing involutions   42     32:45
The quotient-difference algorithm   46     34:16
description of the qd-algorithm   52-56     39:47
the rhombus rules   56     43:00
 3 examples: Catalan numbers, n!, 1. 3 ... (2n-1)   57-59     43:43
the qd-transform   60     45:26
definition of the qd-transform (of a sequence)   61     45:40
4 examples of the qd-transform   62-65     47:37
characterization of the qd-transform   66     50:24
Proof (of the characterizaton of the qd-transform)   69     53:11
Combinatorial proof for the quotient-difference (qd-) algorithm  76     59:09
 Expression with Hankel determinants   86     1:03:03
Complexity of the algorithm, direct algorithm with Motzkin paths   94     1:08:322
Combinatorial applications   100      1:12:32
qd-table for the Catalan numbers   107     1:15:10
The idea of compression of paths for configurartions of non-crossing paths   111     1:17:08
An idea for a research problem   122     1:18:27
The end 127     1:24:35