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 II

Commutations and heaps of pieces with interactions in physics, mathematics and computer science

 

The Institute of Mathematical Sciences, Chennai, India  (January-March 2017)

Ch2  Generating function of heaps of pieces

 Ch 2a

12 January 2017

slides_Ch2a    (pdf   17,6 Mo)      video Ch2a

 

intuitive introduction to generating functions and formal power series  3

the algebra of formal power series  15

operations on combinatorial objects: example with partitions of integers  30

operations on combinatorial objects: formalization  43

        class of combinatorial objects: definition  44

        sum of combinatorial objects  47

        product of combinatorial objects  48

        sequence of combinatorial objects  49

Dyck paths  52

        algebraic equation for Dyck paths  52

        formula for Catalan numbers  57

        historical paper by Catalan  58

        a letter of Euler introducing the Catalan numbers 60,61

        figure of a triangulation of a polygon by Euler 62

        bilateral Dyck path  64

algebraic equation for pyramid of dimers

        semi-pyramids of dimers  67

        exercise: recursive bijection from the algebraic equation of semi-pyramids  76

        exercise: algebraic equation for pyramids of dimers 79

        the end  80

Ch 2b

16 January 2017

slides_Ch2b     (pdf   23 Mo)    video Ch2b                                                                     

 

from the previous lecture  3

bijective proof of an identity on partitions of integers (using symbolic method)  10

        «drawing calculus / computing with drawings»  20

proofs without words  25

visual proof of Pythagoras theorem  27

generating function: rational, algebraic, D-finite  55

first basic lemma on heaps: the inversion lemma  61

        the inversion lemma 1/D  62

        weight of a heap  64

        two extreme cases 69, 70

        proof with the construction of a sign-reversing involution  71-81

extension of the inversion lemma  82

        the inversion lemma N/D

        proof of the inversion lemma  85-94

example: heaps of dimers on a segment  95

        generating function for heaps of dimers on a segment  96

        Fibonacci polynomials  97

        semi-pyramids of dimers on a segment  99

        exercise: formula for the coefficients of the Fibonacci polynomials  100

        historical remarks: Pascal, Fibonacci and Pingala  101-102

exercise: relation between Fibonacci polynomials and Catalan generating function  103

        the identity Fibonacci - Catalan  105

        generating function for pyramids of dimers with given left-width  106

example: heaps of dimers on a cycle  108

        generating function for heaps of dimers on a cycle  111

        Lucas polynomials  112

relation between Fibonacci and Tchebychef polynomials (second kind)  114

relation between Lucas and Tchebychef polyomials (first kind)  120

exercise: a relation between Fibonacci and Lucas polynomials  126

the end  127

Ch 2c

19 January 2017

slides_Ch2c             (pdf    20Mo )        video Ch2c

 

from the previous lecture  3

matching polynomial of a graph G  16

        definition of the matching polynomial  19

        reciprocal of the matching polynomial 21

        generating function for heap of edges on a graph  22

        relations Fibonacci, Lucas and Tchebychef polynomials  23

second proof of the inversion lemma  N/D  26

        factorization in the heap monoid 27

        proof with the «push» operator 28-34

complements: Lazard elimination  36

        elimination of a basic piece in the heap monoid  40

        unique factorization of a pyramid into primitive pyramids 42-45

the inversion lemma 1/D and Möbius function  48

        Möbius classic in number theory  49

Möbius function in posets  50

        incidence algebra of a poset  52

        definitions: zeta and Möbius function in a poset  53

        inversion formula  54

        exercise: computation of the Möbius function of a poset  55

Möbius function in monoids  56

        incidence algebra of a finite factorization monoid  59

        definitions: zeta and Möbius function in a monoid  60

        inversion formulae  61, 62

        exercise: computatin of the Möbius function of a monoid  64

equivalence between Möbius functions in posets and monoids  65

Möbius function and formal series in monoids  71

        back to classical Möbius function in numbers theory  76-78

        Dirichlet serie: Möbius and zeta inverse  80  

Ch2d

23 January 2017

slides_Ch2d          (pdf  17 Mo)        video Ch2d

 

operation on combinatorial objects: derivative  3

the logarithmic lemma  8

        formulation with logarithmic derivative and pyramids generating function  10

        proof of the logarithmic lemma  11-20

        second formulation of the logarithmic lemma  21

the logarithmic lemma: general form  22

        proof with pointed weighted heaps  25-30

        the logarithmic lemma: general form with logarithmic derivative  30

        equivalent formulation  31

        definition: cycles and heaps of cycles  32-34

        example: logarithmic lemma (in general form) for heaps of cycles  36

reminding species and exponential generating functions  (course IMSc 2016, Chapter 3)

        species  39-44

        some examples: permutation, total order, cycle, (set) partition  45-46

        sum of two species  47

        product of two species  48

        example: derangements  49

        substitution in species  50

        «assemblée» of F-structures  52

        weighted species  55

second proof of the logarithmic lemma with exponential generating functions  57

        labeled heaps  59

        «assemblée» of labeled pyramids  62

        end of the second proof of the logarithmic lemma  65

the general form of the logarithmic lemma with exponential generating functions  66

        two examples with pointed heaps of segments and of cycles  68-71

        pointed species and derivative 72

        the general logarithmic lemma for species of heaps of F-structures  73-74 

a last remark  75

the end 78