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 2 The Catalan garden
Ch 2a
21 January 2016
slides Ch2a (pdf 29 Mo)
video Ch2a link to YouTube (1h 21mn)
video Ch2a link to bilibili
The Catalan garden 2 video: 22’‘ video
Binary trees and complete binary trees 7 2’ 33’’ video
binary trees: definition 11 3’ 08’’ video
left - right subtrees, subtrees, left - right child 13 4’ 36’’ video
double, right simple, left simple vertex, leaf 14 5’ 16’‘ video
path in a tree, left-height, right-height, height 15 6’ 07’’ video
left, right principal branch 16 7’ 46’’ video
preorder 17 8’ 24’‘ video
inorder 21 12’ 13’‘ video
postorder 23 13’ 05’’ video
bijection binary trees - complete binary trees 26 15’ 10’’ video
exercise, bijective proof of the multiplicative recurrence
for Catalan numbers 30 16’ 16’’ video
planar trees 31 17’ 21’’ video
preorder 35 20’ 16’’ video
bijection binary trees - (forest of) planar trees 36 21’ 37’’ video
paths: Dyck paths, 2-colored Motzkin paths, Lukasiewicz paths 45 27’ 03’’ video
Motzkin paths 48 28’ 45’’ video
2-colored Motzkin paths 50 30’ 41’’ video
Lukasiewicz paths and langage 51-52 33’ 01’’ video
bijections paths to paths 54 37’ 46’’ video
bijection 2-colored Motzkin paths - Dyck paths 55 38’ 04’’ video
exercise: prove bijectively Touchard’s identity 59 43’ 50’‘ video
bijection Dyck paths - Lukasiewicz paths 60 45’ 16’‘ video
bijections trees to paths 64 49’ 24’’ video
bijection complete binary trees - Dyck paths 65 50’ 14’‘ video
the bijection with violins 70 52’ 55’’ video
the reverse bijection 72 54’ 57’’ video
bijection binary tree - 2-colored Motzkin path 90 56’ 38’’ video
bijection planar trees - Dyck paths 92 58’ 21’’ video
bijection plane trees - Lukasiewicz paths 98 1h 2’ 08’’ video
staircase polygons 103 1h 4’ 40’’ video
bijection staircase polygons - 2-colored Motzkin paths 105 1h 6’ 25’’ video
bijection staircase polygons - Dyck paths 110 1h 10’ 27’’ video
non-crossing partitions 117 1h 14’ 15’’ video
bijection non-crossing partitions - Dyck paths 119 1h 15’ 32’’ video
the end 125 1h 20’ 50’’
Ch 2b
28 January 2016
slides_Ch2b (pdf 22 Mo)
video Ch2b link to YouTube (1h 35mn)
video Ch2b link to bilibili
The Catalan garden 2 10’ video
non-crossing partitions 6 1’ 41’‘ video
bijection non-crossing partitions - Dyck paths 8 3’ 06’‘ video
triangulation of a convex polygon 13 5’ 50’’ video
A letter from Leonhard Euler to Christian Goldbach 15 7’ 33’’ video
Euler polyhedra formula and triangulations 21 9’ 25’’ video
bijection triangulations- complete binary trees 23 12’ 18’’ video
reciprocal bijection 31 15’ 28’’ video
some other interpretations of Catalan numbers: chord diagrams 33 17’ 21’‘ video
bijection chord diagrams -- Dyck paths 36 18’ 25’‘ video
Catalan permutations 40 19’ 48’’ video
permutations sortable by one stack 41 20’ 01’’ video
bijection with Dyck paths 51 21’ 20’’ video
relation Catalan permutations -- non-crossing partitions 52 21’ 50'’ video
forbidden pattern 54 23’ 37’’ video
(312)-avoidig permutations 55 26’ 02’’ video
pairs of sequences 57 28’ 43’‘ video
bijective proof of the multiplicative recurrence for Catalan numbers 60 32’ 51’’ video
bijective proof of Touchard's identity 73 38’ 48’’ video
logarithmic height of a Dyck path 103 44’ 01’’ video
Strahler number of a binary tree 107 46‘ 42‘ video
functional equation for logarithmic height and for Strahler number 108 47‘ 34’‘ video
generating function for Strahler numbers 118 56’ 08’‘ video
the end 119 56’ 20’’ video
complement to Ch 2b: 56’ 20’’ video_Strahler
Strahler number of trees in various sciencesslides_Strahler (pdf 11 Mo)
average of Strahler number 2 56’ 32’’ video
minimum number of registers to compute an arithmetic expression 4 59’ 06’’ video
pebbles problem 7 1h 00’ 14’’ video
bifurcation ratio in hydrogeology 24 1h 02’ 28’’ video
ramification matrix 26 1h 07’ 05’‘ video
DLA and viscuous fingering 28 1h 09’ 56’’ video
galactograms 30 1h 11‘ 34’‘ video
synthetic images of trees 33 1h 12’ 40’‘ video
random binary search tree 40-41 1h 15’ 00’’ video
random binary tree 42 1h 15’ 23’’ video
mixing ramification matrices 44 1h 16’ 01’‘ video
landscape 49 1h 17’ 18’’ video
the end 50 1h 17’ 29’‘ video
complement to Ch 2b: 1h 18’ 00’‘video_Temperley-Lieb
Catalan numbers and Temperley-Lieb algebra TL_n slides_TLn (pdf 5 Mo)
an element of TL_n 2 1h 18’ 19’‘ video
product in TL_n 3 1h 19’ 22’‘ video
generators and relations for TL_n 5 1h 19’ 59’‘ video
heaps of dimers and elements of TL_n 8 1h 23‘ 19’‘ video
condition for a heap of dimers to give an element of a basis of TL_n 13 1h 23’ 57’’ video
staircase decomposition of a heap of dimers 15 1h 25’ 29’’ video
an element of a basis for TL_n 18 1h 27’ 44’’ video
in bijection with a Dyck path 22 1h 31’ 30’’ video
in bijection with a staircase polygon 26 1h 31’ 53’’ video
heap of dimers and permutations 29-30 1h 32’ 20’’ video
an element of a basis for TL_n in bijection with a (321)-avoiding permutation 33 1h 33’ 00’’ video
from a staircase polygon to a (321)-avoiding permutation 34
the end 35 1h 34’ 48’’
Ch 2c
2 February 2016
slides_Ch 2c (pdf 17 Mo)
video Ch2c link to YouTube (1h 21mn)
video Ch2c link to bilibili
the cyclic lemma 3 0’ 07’’ video
conjugate and primitive words 4 0’ 17’’ video
the cyclic lemma 5 3’ 59’’ video
corollary: bijective proof for the formula giving the Catalan number 11 14’ 59’’ video
corollary: formula for -p 12 19’ 00’ 00’’ video
corollary: formula for the alpha distribution (ballot numbers) 13 20‘ 28’‘ video
the ballot problem 15 22' 50'' video
a Catalan triangle 16 24’ 26’’ video
Arbogast tableau 17 27’ 22’‘ video
bijective proofs for Catalan numbers 20 30’ 14’’ video
exercise: bijective proof of (n+1)C_n = binomial (2n,n), solution with binary trees and bilateral Dyck paths 22 31' 10'' video
exercise: find a bijective proof of (n+1)C_n = binomial (2n,n) with only Dyck paths and bilateral Dyck paths 26 33' 35" video
Lagrange inversion formula and the cyclic lemma 27 34’ 21’’ video
some problems on the video between 42’ 20’’ and 43’ 22’’
the reflection principle 40 54’ 32’’ video
the general formula 44 1h 01’ 29’’ video
formula for the double alpha distribution 46 1h 02’ 25’’ video
formula for the alpha distribution 47 1h 03’ 18’‘ video
the reflection principle (again) 48 1h 04’ 03’‘ video
formula for the beta distribution (Narayana numbers) 51 1h 05’ 30’‘ video
three distributions in the Catalan garden 54 1h 09’ 55’’ video
the alpha distribution 55 1h 10’ 06’’ video
the beta distribution 58 1h 12’ 43’‘ video
the gamma distribution 62 1h 16’ 18’‘ video
solution of exercise: semi-pyramids of dimers 65 1h 16’ 30’‘ video
from Dyck paths to semi-pyramids of dimers (video with violin) 70 1h 19’ 55’’ video
the end 73 1h 21’ 15’’
Ch 2d
4 February 2016
slides_Ch2d (pdf 18 Mo)
video Ch2d link to YouTube (1h 27mn)
video Ch2d link to bilibili
from previous lecture: the cyclic lemma 3 00’ 52’’ video
planar maps and the cyclic lemma 10 5’ 11’‘ video
planar maps: definition 11 5‘ 30’‘ video
rooted planar maps: definition 12 6’ 03’‘ video
Tutte formula for the number of rooted planar maps 13 6‘ 21’‘ video
blossoming trees 16 9‘ 14’‘ video
bijection planar maps -- quartic planar maps 18 10‘ 35’‘ video
reverse bijection 22 15’ 02’’ video
Schaeffer’s bijection between well balanced blossoming trees and quartic rooted maps 25 17‘ 13’’ video
blossoming trees 27 17’ 39’‘ video
border word 28 17’ 57’‘ video
partial closure of a blossoming tree 37 21’ 24’‘ video
well-balanced blossoming tree: definition 42 25’ 24’‘ video
complete closure of a well-balanced tree 44 29’ 07’‘ video
introduction to q-analogues with q-Catalan 53 33’ 52’‘ video
q-binomial coefficients 56 37‘ 29’‘ video
the maj q-Catalan 57 40‘ 05’‘ video
the area q-Catalan 60 43’ 54’‘ video
Polya q-Catalan 63 47’ 00’’ video
complement: (q,t)-Catalan 64 49’ 04’’ video
the bounce parameter 65 49’ 34’‘ video
the (q,t)-Catalan polynomial 68 53‘ 28’‘ video
complement to the complement: original definition by Garsia-Haiman 70 56’ 21’’ video
some exercises using Catalan factorization and Catalan words 75 58’ 18’’ video
Catalan factorization of a word 76 58’ 36’’ video
Catalan word and the bijection theta 78 1h 00’ 41’’ video
the bijection rho 80 1h 03’ 46’‘ video
exercise: average height of the final point of left factors of Dyck paths 83 1h 06’ 33’’ video
exercise: average area of Dyck paths 84 1h 07’ 44’’ video
exercise: average path length of a binary tree 86 1h 09’ 18’’ video
exercise: average length of the left branch of a random binary tree 88 1h 10’ 54’’ video
complement: the TASEP 89 1h 11’ 20’’ video
Markov chain and stationary probabilities 93 1h 14’ 51’’ video
path interpretation of the stationary probabilities of the TASEP 96 1h 15’ 59’’ video
canopy of a binary tree 97-98 1h 17’ 34’’ video
interpretation of the stationary probabilities with binary trees 99 1h 19‘ 03’‘ video
exercise: formula for the partition function of the TASEP 103 1h 21‘ 20’‘ video
bijection pair of paths -- binary trees preserving the canopy 100 1h 22’ 21’’ video
the end 104 1h 26’ 31’’