The Art of Bijective Combinatorics Part I
An introduction to enumerative, algebraic and bijective combinatorics
The Institute of Mathematical Sciences, Chennai, India (January-March 2016)
Ch 1 Ordinary generating functions
Ch 1a
7 January 2016
slides Ch1a (pdf 26 Mo)
video Ch1a link to YouTube (1h 22mn)
video Ch1a link to bilibili
an example: binary trees slide: 3 25
Euler triangulations 13 6:24
intuitive introduction to ordinary generating functions and formal power series 17 9:45
a little exercise: Fibonacci generating function 23 11:11
formal power series algebra: formalisation 29 13:24
algebra of formal power series 33 15:25
summable family 35 18:13
infinite product 38 20:45
other operations 40 22:12
free monoid and non-commutative power series 44 28:05
operations on combinatorial objects, intuitive introduction with binary trees 47 32:10
operations on combinatorial objects, formalisation 55 37:31
sum 59 47:12
product 60 48:23
sequences 61 50:00
operations on combinatorial objects, example: integer partitions, q-series 63 51:28
generating function for (integer) partitions 73 58:39
execrcise: D-partitions 74 59:50
Rogers-Ramanujan identities 76 1:02:54
bijective proof of an identities 82 1:08:21
visual proof:Pythagore 84 1:09:01
bijective proof of an identity, the bijective paradigm 112 1:10:12
bijective combinatorics, example: Catalan numbers 126 1:14:15
Dyck paths 133 1:19:07
the end 139 1:22:40
Ch 1b
12 January 2016
slides Ch1b (pdf 20 Mo)
video Ch1b link to YouTube (1h 22mn)
video Ch1b link to bilibili
from the previous lecture slide:3 0:05
operation on combinatorial objects, derivative 16 4:45
operation on combinatorial objects, derivative, example: heaps of dimers 20 10:58
heaps of dimers: definition 21 11:22
the logarithmic lemma for heaps of dimers 18:40
pyramid and maximal piece: definition 19:24
proof of the logarithmic lemma for heaps of dimers 28 22:30
exercises: pyramids and algebraic generating functions 37 29:56
semi-pyramids of dimers 38 30:07
pyramids of dimers 41 32:17
bilateral Dyck paths 42 34:07
operation on combinatorial objects, substitution, example: Strahler number of a binary tree 44 37:49
substitution 45 38:26
Strahler number of a binary tree: definition 47 42:00
Hydrogeology 49-51 44:37
functional equation for two variables generating function of Strahler number 52 47:19
experimental combinatorics 53-59 50:02
Pascal, Pingala and Fibonacci 60 55:34
substitution in binary trees 65-72 58:21
generating functions: rational, algebraic, D-finite 76 1:05:05
rational generating functions 79 1:09:13
weighted paths 81 1:09:45
self-avoiding path and circuit 83 1:11:48
elementary circuit and cycles 84 1:12:24
main proposition: generating function for weighted paths in a graph as N_(i,j)/D 86 1:13:47
linear algebra proof of the main proposition 87-91 1:18:25
the end 92 1:22:31
Ch 1c
14 January 2016
slides Ch1c (pdf 20 Mo)
video Ch1c link to YouTube (1h 24mn)
video Ch1c link to bilibili
from the previous lecture slide: 3 15’‘
bijective proof of the identity N_(i,j)/D 9 3’ 09’‘
construction of the involution phi 12 9’ 49’‘
an example and an exercise for N_(i,j/)D 19 25’ 30’‘
an example: paths on a graph with 2 vertices 20 25’ 36’‘
exercise: directed path 21 28’ 24’‘
another example for N_(i,j)/D: bounded Dyck paths 23 32’ 03’‘
Fibonacci polynomials and matchings 30 36’ 31’‘
Fibonacci polynomials 34 39’ 55’‘
generating functions for Fibonacci polynomials 37 40’ 30’‘
exercise: coefficient of the Fibonacci polynomials 39 45’ 38’‘
Pingala and Fibonacci 40-41 46’ 18’‘
exercise: Fibonacci numbers and polyominoes 42 49’ 02’‘
Fibonacci and Tchebychef polynomials 44 53’ 08’‘
Lucas and Tchebychef polynomials 50 59’ 25’‘
exercise: relation Fibonacci and Lucas polynomials 55 1h 3’ 10’‘
complement: matching polynomial of a graph 56 1h 3’ 45’‘
zeros of the matching polynomial of a graph 60 1h 5’ 53’‘
exercise: coefficients of the Hermite and Laguerre polynomials 63 1h 8’ 40’‘ video
example of N_(i,j)/D, back to Strahler number 64 1h 8’ 58’’
logarithmic height of a Dyck path 68 1h 9’ 58’‘
generating function for Strahler numbers 74 1h 16’ 08’‘
exercise, proof by killing involution: Euler’s pentagonal theorem 76 1h 17’ 55’‘
the end 81 1h 24’18’’
Ch 1d
19 January 2016
slides Ch1d (pdf 24 Mo)
video Ch1d link to YouTube (1h 22mn)
video Ch1d link to bilibili
from the previous lecture, proof of the Euler’s pentagonal theorem slide 3 15’‘
another exercise with a sign reversing involution
(generating function for heaps of dimers on a segment) 14 10’ 35’‘
more about rational series 16 12’ 57’‘
zeros of Fibonacci polynomials 19 17’ 30’‘
zeros of Lucas polynomials 20 18’ 40’‘
Lagrange inversion formula 21 19’ 01’‘
algebraicity with hidden decomposable structures, example: planar maps 25 26’ 36’‘
system of equations for rooted planar maps and the bijection Cori-Vauquelin 31 32’ 03’‘
direct formula for the number of rooted planar maps 33 34’ 18’‘
blossoming trees and idea of Schaeffer bijection 37 36’ 21’’
complements: algebraicity with hidden decomposable structures, example: directed animals 41 38’ 35’’
system of equations for directed animals 44 40’ 57’’
exercise: system of equations for prefix of Motzkin paths 45 41’ 25’‘
random directed animals 47-48 45’ 49’‘
an anecdote (about directed animals) 49 46’ 18’‘
complements: algebraicity with hidden decomposable structures, example: convex polyominoes 54 49’ 31’’
exercise: directed and vertically convex polyominoes 59 50’ 22’‘
formula for the number of convex polyominoes with given perimeter 64 52’ 50’‘
random convex polyominoes (with fixed perimeter) 66 53’ 31’‘
random convex polyominoes (with fixed area) 67-68 54’ 17’‘
rational and algebraic generating functions, a flavor of theoretical computer science,
Schützenberger’s methodology coding with words of algebraic languages 69 54’ 51’‘
algebraic language and algebraic grammar 70 55’ 22’’
non-ambiguous grammar for the Dyck language, derivation tree 73 1h 3’ 05’‘
Chomsky-Schützenberger theorem 75 1h 5’ 29’‘
algebraic equation for prefix of Motzkin paths 76 1h 9’ 54’‘
automaton and rational language 77 1h 10’ 09’‘
generating functions, algebraic, D-finite or not D-finite ? 81 1h 15’ 26’‘
paths in a quadrant 83 1h 16’ 16’’
Kreweras and Gessel paths 84 1h 17’ 29’‘
catalytic variables and kernel methodology 85 1h 18’ 12’‘
the queen 1h 20’ 45’‘
an example of generating function not D-finite: connected heaps of dimers 87 1h 21’ 25’‘
the end 88 1h 22’ 18’’