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 Ekalavya (IMSc Media Center)
video Ch3a link to YouTube (from IMSc Matsciencechanel Playlist)
video Ch3a link to bilibili
Dedication to Philippe Flajolet 3 00:10
Euler, Ramanujan and Knuth 4
happy new year card 2009 5
ALEA group, Séminaire Flajolet 6
analytic combinatorics 7
Arithmetic continued fractions 9 4:48
golden number, Fibonacci numbers 10-11
Apéry continuedd fraction 12 6:32
Some ananlytic continued fractions 13 7:13
Euler 15-17 7:40
Ramanujan 21 11:34
Reminding formal power series, formalisation (Part I, Ch1a, 29-46) 24 12:58
Reminding operations on combinatorial objects, formalisation (Part I, Ch1a, 55-62, 63-75) 32 16:28
Analytic continued fraction 54 25:46
Jacobi, Stieljes, equivalence with orthogonal polynomials
The fundamental Flajolet Lemma 60 30:22
Proof of Flajolet Lemma 67 33:58
Continued fractions and orthogonal polynomials 77 39:04
Example: Laguerre polynomials and continued fractions 83 40:21
Convergents 88 43:41
expression of the convergents with reciprocal of orthogonal polynomials 93 45:33
Convergents: linear algebra proof (Part I, Ch1b, 79-91) 95 46:45
weighted Motzkin paths and tridiagonal matrix 98 48:40
Convergents: bijective proof (with a sign reversing involution) 102 52:30
Back to the bijective proof of the inversion formula N_i,j/D (Part I, ch1c, 10-18) 106 55:53
Some extensions of the fomula expressing the convergents (of a Jacobi continued fraction) 113 57:12
generating function for weighted Motzkin paths bounded at level k, starting at level r and ending at level s 114-115
particular case 116 s=0, r=k1:00:47
corollary: a classical formula on orthogonal polynomials 117 1:01:31
Contraction of continued fractions 118 1:04:35
2 bijections Dyck paths -- 2-colored Motzkin path 121-126 1:05:30
first relation between the coefficients of Stilejes and Jacobi continued fractions 130 1:09:35
second relation between the coefficients of Stilejes and Jacobi continued fractions 134 1:11:26
Some examples 135 1:12:13
secant and tangent numbers, Euler, Genocchi numbers
Complements: elliptic functions 150 1:20:11
Jacobi elliptic function sn, cn, dn, Apéry continued fraction, Fermat curve, Dixon elliptic function sm, cm,
Conrad continued fraction, Polya urn model, pseudofactorial, lattice sum and Weierstrass function
Philippe's card for happy new year 2010 (work with R. Bacher, The Ramanujan Journal) 160 1:24:38
Philippe and Sanscrit 161 1:25:01
The end 162 1:25:44
see also the paper:
X.G. Viennot (2013) Introduction to Chapter 3 on continued fraction, A survey of the 18 papers of P. Flajolet on continued fractions,
Volume V, Chapter 3 of Philippe Flajolet's collected works.
Chapter 3b
February 14 , 2019
slides of Ch3b (31 Mo pdf )
video Ch3b link to Ekalavya (IMSc Media Center)
video Ch3b link to YouTube (from IMSc Matsciencechanel Playlist)
video Ch3b link to bilibili
Reminding Ch 3a 3 00:22
Continued fractions: other examples 15 04:10
beta-Tchebychev (Narayan numbers) 16 04:22
Schröder numbers 21 08:58
Polya q-numbers (staircase polygons or parallelogram polyominoes) 26 13:38
directed animals 31 17:07
Subdivided Laguerre histories 38 20:24
Bijection subdivided Laguerre histories -- permutations (A. de Médicis, X.V.) 44 23:44
pair of Hermite histories 46-47 25:24
pair of chords diagrams 48-66 28:24
from pair of chords diagram to permutations 67-68 31:38
discussion 34:59
Reverse bijection: from permutations to subdivided Laguerre histories 69 37:58
Contraction of continued fractions 73 41:39
from Stieljes to Jacobi continued fraction for the generating function of n! 80 42:43
the idea of contraction in Laguerre histories 81-82 43:57
From subdivided Laguerre histories to (restricted) Laguerre histories 83 45:55
i.e. contraction in Laguerre histories
the final diagram: subdiveded and restricted Laguerre histories with the pair of Hermite histories 91-92 48:59
Combinatorial proof of another Euler's continued fraction 93 51:09
i.e. Stilejes continued fraction for the generating function of permutations with the parameter beta (number of cycles)
Bijection subdivided Laguerre histories -- Dyck tableaux 98 54:18
Dyck tableaux: definition (Aval, Boussicault, Dasse-Hertaut) 99 54:37
From restricted Laguerre histories to Laguerre heaps (of segments) 104 59:12
From Laguerre heaps to permutations 107 1:00:30
From permutations to Dyck tableaux 113 1:02:25
From Dyck tableaux to subdivided Laguerre histories 126 1:04:04
commutative diagram ! 128 1:04:08
From restricted Laguerre histories to permutations (word notations) 129 1:04:51
second commutative diagram 131 1:07:37
the whole commutative diagram of Ch 3b 133-134 1:07:59
Sokal-Zeng's 10 parameters continued fraction (SLC 81) 135 1:09:14
Laguerre hepas of segments with 12 parameters for the moments (or continued fraction) 136 1:10:34
Interpretation (of continued fractions) with heaps of monomers and dimers 137 1:12:18
weighted semi-pyramid of monomers-dimers 138-139 1:12:44
semi-pyramid of monomers-dimers as a sequence of primitive semi-pyramids 140-141 1:14:03
generating function of weighted semi-pyramids of monomers-dimers as a Jacobi continued fraction 142-143 1:15:03
convergents and inversion theorem for heaps of monomers-dimers 144-147 1:15:40
The end 148 1:18:57
Complementary lectures 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 Ekalavya (IMSc Media Center)
video link to YouTube (from IMSc Matsciencechanel Playlist)
video link to bilibili
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.
"Combinatorial aspects of continued frations and applications"
Colloque PFAC, "Philippe Flajolet and analytic combinatorics", Paris, 15 December 2011
slides (pdf, 20 Mo)
abstract
In his 1980 seminal paper, Philippe Flajolet stated a fundamental theorem interpreting any analytic continued fractions in terms of certain weighted lattice paths (the so-called Motzkin paths). This theory is equivalent to give an interpretation of the moments of any family of orthogonal polynomials in term of these weighted paths. Combining this general statement with some specific bijections between classical combinatorial objects and the so-called "histories" related to weighted Motzkin paths, Flajolet deduce several combinatorial proofs for many continued fraction expansions of well known power series. In particular the classical "Françon-Viennot bijection" between permutations and "Laguerre histories" play a key role and give rise to a combinatorial theory of the Sheffer class of orthogonal polynomials (i.e. Hermite, Laguerre, Charlier, Meixner I and II).
Using Françon's concept of "data histories", a spectacular application of this combinatorial theory of continued fraction has been made by P. Flajolet (with J. Françon and J. Vuillemin) for the evaluation of the integrated cost of data structures subject to arbitrary sequences of insert, delete and search operations. Each classical data structures is related to a classical family of Sheffer type polynomials.
Extensions of the theory has been made by E. Roblet for Padé approximants and T-fractions. Further combinatorial developments have been made more recently by P. Flajolet with E. van Fossen Conrad and R. Bacher for continued fractions expansions of some elliptic functions. Some recent applications are also related to physics with some discrete integrable systems and positivity in cluster algebras involving continued fraction rearrangements (P. Di Francesco and R. Kedem) or the work of J. Bouttier and E. Guitter relating random planar maps and continued fractions. One of the last paper of Philippe (with P. Blasiak) connects continued fractions with the normal ordering of creation-annihilation operators in quantum physics.