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