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