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