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.