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 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.