Course  X.V.  IMSc 2017


Course  IMSc  Chennai, India

January-March 2017

Ch2  Generating function of heaps of pieces


             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


            16 January 2017

                           slides_Ch2b     (pdf   23 Mo)    video Ch2b  

                                                                            available since 3 Feb

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



          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 



        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

go to:

the IMSc 2016 bijective course website

courses  website

main Xavier Viennot  website