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