• XAVIER VIENNOT
  • Foreword
    • Preface
    • Introduction
    • Acknowledgements
    • Lectures for wide audience
  • PART I
    • Preface
    • 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
    • Lectures related to the course
    • List of bijections
    • Index
  • PART II
    • Preface
    • 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
    • Lectures related to the course
  • PART III
    • Preface
    • 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
    • Preface
    • 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   The algebra of formal power series, operations on combinatorial objects, Dyck paths, algebraic equation for pyramids of dimers,
bijection Dyck paths -- semi-pyramids of dimers

12 January 2017
slides_Ch2a    (pdf   17,6 Mo)    
video Ch2a  link to YouTube
video Ch2a  link to bilibili
Intuitive introduction to generating functions and formal power series  3     0:56
The algebra of formal power series  15     4:26
Operations on combinatorial objects: example with partitions of integers  30     12:13
Operations on combinatorial objects: formalization  43     22:29
        class of combinatorial objects: definition  44     22:46
discussion     24:52
condition (*)     44     26:28
example: "size" of a combinatorial object   46     29:44
        sum of combinatorial objects  47     32:15
        product of combinatorial objects  48     32:47
        sequence of combinatorial objects  49     33:33
symbolic method (Flajolet, Sedgewick)   50
Dyck paths  51     34:20
definition: Dyck path   52     
        algebraic equation for Dyck paths  53     36:40
        formula for Catalan numbers  57     37:48
        historical paper by Catalan  58     37:59
        a letter of Euler introducing the Catalan numbers  60-61     38:16
        figure of a triangulation of a polygon by Euler  62     39:42
        bilateral Dyck path  64     40:13
Algebraic equation for pyramid of dimers   66     41:07
        semi-pyramids of dimers  67     41:25
algebraic equation for semi-pyramids of dimers   70-73     41:53
[some corrections of the original slides in the video]
        exercise: from the algebraic equation, construction of a recursive bijection between Dyck paths and semi-pyramids of dimers  76     44:15
pyramids of dimers on Z, bijection with some bilateral Dyck paths       77-78     45:14
        exercise: algebraic equation for pyramids of dimers 79     45:44
        the end  80     46:21

Ch 2b   Inversion Lemma 1/D, extension N/D, Fibonacci, Lucas and Tchebychef polynomials

16 January 2017
slides_Ch2b     (pdf   23 Mo)  
video Ch2b  link to YouTube
video Ch2b  link to bilibili                                                                    
From the previous lecture  3     0:10
Bijective proof of an identity on partitions of integers (using symbolic method)  10     4:50
        «drawing calculus / computing with drawings»  20     8:03
Proofs without words  25     9:21
Visual proof of Pythagoras theorem  27     9:50
Generating function: rational, algebraic, D-finite  55     11:00
First basic lemma on heaps: the inversion lemma  61     17:06
       trivial heaps, the inversion lemma 1/D (in symbolic notations)  62     17:32
        weight of a heap  64     18:19
the inversion lemma 1/D   65     19:48
        two extreme cases 69-70     21:00
        proof with the construction of a sign-reversing involution  71-81     22:30
Extension of the inversion lemma  85     31:39
        the inversion lemma N/D   86      
        proof of the inversion lemma  88-97     33:35
Example: heaps of dimers on a segmen  98     39:49
        generating function for heaps of dimers on a segment  99     39:53
        Fibonacci polynomials  100     40:18
        semi-pyramids of dimers on a segment  102     42:09
        exercise: formula for the coefficients of the Fibonacci polynomials  103     43:12
        historical remarks: Pascal, Fibonacci and Pingala  104-105     43:42
Exercise: relation between Fibonacci polynomials and Catalan generating function  106     45:45
some notations: D and Q   107     46:19
        the identity Fibonacci - Catalan  108     46:47
        generating function for pyramids of dimers with given left-width  109     47:38
Example: heaps of dimers on a cycle  111     50:44
        generating function for heaps of dimers on a cycle  114     51:10
        Lucas polynomials  115     51:24
Relation between Fibonacci and Tchebychef polynomials (second kind)  117     52:21
Relation between Lucas and Tchebychef polyomials (first kind)  123     58:00
Exercise: a relation between Fibonacci and Lucas polynomials  129     1:00:28
The end  130     1:01:21

Ch 2c   Matching polynomial of a graph, second proof of N/D, Lazard elimination, Möbius function in monoids and posets

19 January 2017
slides_Ch2c     (pdf    20Mo )      
video Ch2c  link to YouTube
video Ch2c  link to bilibili
From the previous lecture  3     0:10
Matching polynomial of a graph G  16     16:30
definition: matching of a graph   17-18     16:57
        definition of the matching polynomial  19     17:35
        reciprocal of the matching polynomial 20-21     20:27
discussion   21:56
        generating function for heaps of edges on a graph  22     24:21
        relations Fibonacci, Lucas and Tchebychef polynomials  23     26:42
Second proof of the inversion lemma  N/D  26     30:51
        proposition: factorization in the heap monoid 27     31:05
        proof with the «push» operator 28-34     32:34
end of the second proof of the inversion lemma   35     34:44
Complements: "Lazard elimination"  36     35:46
idea of "Lazard elimination" (Duchamp, Krob)   37     36:18
example with free monoids   38     37:52
        elimination of a basic piece in the heap monoid  40-41     39:44
        unique factorization of a pyramid into primitive pyramids 42-45      41:21
recalling Lazard elimination for free group and free Lie algebra   46     42:38
discussion  43:14
evocation of free partially commutative Lie algebra  (Lalonde, Duchamp, Krob)   47     44:52
The inversion lemma 1/D and Möbius function  48     46:09
        Möbius classic in number theory  49     47:03
Möbius function in posets  50     50:02
definition: locally finite posets   51     50:33
incidence algebra     51:09
        definition: incidence algebra of a poset  52     51:45
        definitions: zeta and Möbius function in a poset  53     54:22
        inversion formula  54     56:03
        exercise: computation of the Möbius function of a poset  55     58:12
Möbius function in monoids  56     59:11
finite factorization monoid   57-58     59:54
        incidence algebra of a finite factorization monoid  59     1:02:32
discussion     1:03:42
        definitions: zeta and Möbius function in a monoid  60     1:05:54
        inversion formulae  61, 62     1:08:01
notations: d+(x),  d-(x)   63     1:11:06
        exercise: computatin of the Möbius function of a monoid  64     1:12:11
discussion   1:13:19
Equivalence between Möbius functions in posets and monoids  65     1:14:53
from monoids to posets   66-67     1:14:59
from posets to monoids   68-70     1:17:39
Möbius function and formal series in monoids  71     1:19:42
        back to classical Möbius function in numbers theory  76-78     1:22:15
        Dirichlet serie: Möbius and zeta inverse  80     1:23:54
The end   81     1:24:55

Ch2d   The logarithmic lemma, second proof with exponential generating function, general form with species of heaps of F-structures

23 January 2017
slides_Ch2d          (pdf  17 Mo)      
video Ch2d  link to YouTube
video Ch2d  link to bilibili
The logarithmic lemma, operation on combinatorial objects: derivative  3    
(reminding) class of weighted combinatorial objects    4     0:55
derivative lemma   6     8:30
the logarithmic lemma  8     11:18
weight of heap   9     11:26
        formulation with logarithmic derivative and pyramids generating function  10     12:18
        (visual) proof of the logarithmic lemma  11-20     13:18
        second formulation of the logarithmic lemma  21     16:42
The logarithmic lemma: general form  22     19:31
the class of pointed weighted heaps   25-26     24:45
        proof with pointed weighted heaps  27-30     
        the logarithmic lemma: general form with logarithmic derivative  30     29:54
        equivalent formulation  31     31:52
        definition: cycles and heaps of cycles  32-34     32:42
        example: heaps of cycles (visualization)  35     35:35
example: logarithmic lemma (in general form) for heaps of cycles   36     36:48
discussion    37:40
Second proof of the logarithmic lemme with exponential generating funcitons   37     41:32
reminding species and exponential generating functions  (course IMSc 2016, Chapter 3)    38  
        species  39-44     42:17
        some examples: permutation, total order, cycle, (set) partition  45-46     48:02
        sum of two species  47     51:13
        product of two species  48     52:44
        example: derangements  49     57:02
        substitution in species  50     59:18
        «assemblée» of G-structures  52     1:02:46
        weighted species  55     1:05:59
Second proof of the logarithmic lemma with exponential generating functions  57     1:07:40
        labeled heaps  59     1:07:50
        «assemblée» of labeled pyramids  62     1:09:34
The general form of the logarithmic lemma with exponential generating functions  66     1:12:49
        two examples with pointed heaps of segments and of cycles
        interpretation with pointed species and derivative 72     1:15:55
        the general logarithmic lemma for species of heaps of F-structures  73-74     1:16:53
A last remark  75     1:18:10
The end 78     1:24:30